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 = 3Output:false

**Example 2:**

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

**Example 3:**

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

**Note:**

- The number of nodes in the tree will be between
`2`

and`100`

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