# Cousins in Binary Tree

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

BFS Approach

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     public int val;
*     public TreeNode left;
*     public TreeNode right;
*     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
public class Solution {
public bool IsCousins(TreeNode root, int x, int y) {

//Base case
if(root == null)
return false;

Queue<TreeNode> q = new Queue<TreeNode>();

q.Enqueue(root);

while(q.Count > 0)
{
int size = q.Count;
bool xExists = false;
bool yExists = false;

for(int i=0;i<size;i++)
{
TreeNode cur = q.Dequeue();
if(cur.val == x)
xExists = true;
if(cur.val == y)
yExists = true;

//Condition to check direct child of parent to return false
if(cur.left != null && cur.right != null)
{
if(cur.left.val == x && cur.right.val == y)
return false;
if(cur.left.val == y && cur.right.val == x)
return false;
}

if(cur.left != null)
q.Enqueue(cur.left);
if(cur.right != null)
q.Enqueue(cur.right);
}

if(xExists && yExists)
return true;
else if(xExists || yExists)
return false;
}

return false;
}
}```

Time Complexity: O(n)

Space Complexity: O(n)