LeetCode: Cousins in Binary Tree

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

Example 1:

Input: root = [1,2,3,4], x = 4, y = 3
Output: false

Example 2:

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:

1. The number of nodes in the tree will be between 2 and 100.
2. Each node has a unique integer value from 1 to 100.

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 and y
• parent of x and y

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.