Problem Statement
In a binary tree, the root node is at depth 0
, and children of each depth k
node are at depth k+1
.
Two nodes of a binary tree are cousins if they have the same depth, but have different parents.
We are given the root
of a binary tree with unique values, and the values x
and y
of two different nodes in the tree.
Return true
if and only if the nodes corresponding to the values x
and y
are cousins.
Example
Input: root = [1,2,3,4], x = 4, y = 3
Output: false
Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true
Example 3:
Input: root = [1,2,3,null,4], x = 2, y = 3
Output: false
Note:
 The number of nodes in the tree will be between
2
and100
.  Each node has a unique integer value from
1
to100
.
Solution Thought Process
When we hear of any kind of distance in trees, the first thing we should think about running a BFS.
For applying the BFS, we need the following data structures 

queue<TreeNode*>curr_depth_nodes
 a queue for maintaining the tree nodes in BFS. 
vector<int>depth(101,0)
 a vector for storing depth of each node value, initially all values are set to 0. 
int parent_x = 1, parent_y = 1
 two integers for storing parent of x and y respectively.
The BFS algorithm starts with root and enqueues it. The initial root depth is assigned as 0
. Then it dequeues it and enqueues it's children to the queue. When we dequeue the children, children's children are enqueued and it goes on and on. The main difference with DFS and BFS is: in BFS, at first we visit all the nodes of same depth, whereas in DFS, we get to visit the lowest depth and working our way up.
So when we are dequeuing our node, we check if it has any children (left node or right node). If it has any children, then we set the distance with this formula
depth[children] = depth[parent] + 1;
Thus the depth of children gets populated from the depth of parent.
Next, we check if any of the children is equal to x
or y
. If they are equal to anyone of them, we store the parent_x
or parent_y
So, we have got the things we needed to make the decision:
 depth of all nodes which has the depth of
x
andy
 parent of
x
andy
If the depth of x and y are the same and not 0 and the parents are different, we return true, otherwise, our answer is false.
Solution
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isCousins(TreeNode* root, int x, int y) {
queue<TreeNode*>curr_depth_nodes;
vector<int>depth(101,0);
int parent_x = 1, parent_y = 1;
curr_depth_nodes.push(root);
depth[root>val] = 0;
while(!curr_depth_nodes.empty())
{
auto curr = curr_depth_nodes.front();
curr_depth_nodes.pop();
if(curr)
{
if(curr>left)
{
depth[curr>left>val] = depth[curr>val]+1;
curr_depth_nodes.push(curr>left);
if(curr>left>val == x)
{
parent_x = curr>val;
}
if(curr>left>val == y)
{
parent_y = curr>val;
}
}
if(curr>right)
{
depth[curr>right>val] = depth[curr>val]+1;
curr_depth_nodes.push(curr>right);
if(curr>right>val == x)
{
parent_x = curr>val;
}
if(curr>right>val == y)
{
parent_y = curr>val;
}
}
}
}
if(parent_x != parent_y && depth[x] != 0 && depth[y] != 0 && depth[x] == depth[y])
{
return true;
}
return false;
}
};
Complexity
Time Complexity: O(V+E), V is the number of vertices and E is the number of edges. For each node, we have to visit all it's edges.
Space Complexity: O(V), in the worst case we have to hold all of the vertices.
Top comments (0)