LeetCode: Cousins in Binary Tree
Tags: datastuctures, algorithms, leetcode, bfs
Published: 2020-05-08 07:15:01

---
title: LeetCode: Cousins in Binary Tree
published: true
description: 07.05.2020
tags: datastuctures, algorithms, leetcode, bfs
series: LeetCode May Challenge
---


### 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:
![img](https://assets.leetcode.com/uploads/2019/02/12/q1248-01.png)**

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

**Example 2:
![img](https://assets.leetcode.com/uploads/2019/02/12/q1248-02.png)**

```
Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true
```

**Example 3:**

**![img](https://assets.leetcode.com/uploads/2019/02/13/q1248-03.png)**

```
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

```c++
/**
 * 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.