Given the root of a binary tree with unique values and the values of two different nodes of the tree x and y, return true if the nodes corresponding to the values x and y in the tree are cousins, or false otherwise.

Two nodes of a binary tree are cousins if they have the same depth with different parents.

Note that in a binary tree, the root node is at the depth 0, and children of each depth k node are at the depth k + 1.

&nbsp;
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


&nbsp;
Constraints:


	The number of nodes in the tree is in the range [2, 100].
	1 &lt;= Node.val &lt;= 100
	Each node has a unique value.
	x != y
	x and y are exist in the tree.


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    ans = False
    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
        def dfs(node, depth):
            if self.ans or not node: return 0
            if node.val == x or node.val == y: return depth
            l = dfs(node.left, depth+1)
            r = dfs(node.right, depth+1)
            if not (l and r): return l or r
            if l == r and l != depth + 1: self.ans = True
            return 0
        
        dfs(root, 0)
        return self.ans
class Solution {
    public boolean isCousins(TreeNode root, int x, int y) {
        Set<TreeNode> parentSet = new HashSet<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);

        while (!q.isEmpty()) {
            int len = q.size();

            for (int i = 0; i < len; i++) {
                TreeNode parent = q.remove();

                for (TreeNode child : new TreeNode[]{parent.left, parent.right}) {
                    if(child != null) {
                        q.add(child);
                        if (child.val == x || child.val == y)
                            parentSet.add(parent);
                    }
                }
            }
            if (parentSet.size() > 0)
                return parentSet.size() == 2; //if same parent -> set size wil be 1
        }
        return false;
    }
}
class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        if(root -> left == NULL || root -> right == NULL) return false;
        //to store node with parent
        queue<pair<TreeNode*, TreeNode*> > q;
        //push root
        q.push({root, NULL});
        //push NULL for level seperation
        q.push({NULL, NULL});
        //boolean val to know if we found x or y yet during traversal of tree
        pair<bool, TreeNode*> foundx = {false, NULL}, foundy = {false, NULL};
        
        //start the level order traversal
        while(!q.empty()){
            TreeNode* top = q.front().first;
            TreeNode* parent = q.front().second;
            q.pop();
            
            //when a level is completely traversed
            if(top == NULL){
                //if we found both x and y and if their parent are not same we found cousins
                if(foundx.first && foundy.first && foundx.second != foundy.second) return true;
                //if one of them found when other not, or when both were found and their parent were equal
                if(foundx.first || foundy.first) return false;
                //push another NULL for further level seperation, if there are any.
                if(!q.empty()) q.push({NULL, NULL});
            }
            else{
                //find x and y
                if(top -> val == x) foundx = {true, parent};
                if(top -> val == y) foundy = {true, parent};
                
                //push current node's childs with parent as current node.
                if(top -> left) q.push({top -> left, top});
                if(top -> right) q.push({top -> right, top});
            }
        }
        return false;
    }
};
var isCousins = function(root, x, y) {
    let xHeight = 1;
    let xParent = null;
    let yHeight = 1;
    let yParent = null;
    
    const helper = (node, depth, parent) => {
        if(node === null)
            return null;
        
        helper(node.left, depth + 1, node);
        helper(node.right, depth + 1, node);
        
        let val = node.val;
        
        if(val === x) {
            xHeight = depth;
            xParent = parent;
        }
        
        if(val === y) {
            yHeight = depth;
            yParent = parent;
        }
    }
    
    helper(root, 0);
    
    return xHeight === yHeight && xParent !== yParent ? true : false;
};
Cousins in Binary Tree