Problem

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.

Definition

Cousins in Tree Definition

Examples

Example 1:

    1
   / \
  2   3
 /
4

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

Example 2:

    1
   / \
  2   3
 /
4

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

Example 3:

    1
   / \
  2   3
   \   \
    4   5

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

More examples

graph TD;
1 --> 2 & 3
2 --> 4 & 5
3 --> 6 & 7
4 --> 8 & 9
6 --> 12 & 13
  
x = 1, y = 2, false
x = 2, y = 3, false
x = 3, y = 4, false
x = 4, y = 6, true
x = 8, y = 12, true

Similar Problem

Cousins in Binary Tree 2 Problem

Solution

Method 1 - Level order traversal

To determine if two nodes are cousins, we need to know:

  1. The depth of each node.
  2. The parent of each node.

Using level-order traversal (BFS) is suitable as it allows us to naturally track the depth of nodes. During the traversal, we can record the depth and parent of each node. With this information, we can later check the conditions for nodes x and y to be cousins.

Here is the approach:

  1. Level-Order Traversal (BFS):
    • Use a queue to perform BFS. Track the parent and depth of each node as we visit them.
    • Initialize the queue with the root node and depth 0.
    • For each node, record its children with the incremented depth and the current node as their parent.
  2. Check Conditions for Cousins:
    • After the traversal, check if nodes x and y have the same depth but different parents.

Code

Java
public class Solution {
    public boolean isCousins(TreeNode root, int x, int y) {
        if (root == null) return false;

        Map<Integer, Integer> depth = new HashMap<>();
        Map<Integer, TreeNode> parent = new HashMap<>();

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        depth.put(root.val, 0);
        parent.put(root.val, null);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            
            if (node.left != null) {
                queue.offer(node.left);
                depth.put(node.left.val, depth.get(node.val) + 1);
                parent.put(node.left.val, node);
            }
            
            if (node.right != null) {
                queue.offer(node.right);
                depth.put(node.right.val, depth.get(node.val) + 1);
                parent.put(node.right.val, node);
            }
        }

        return depth.get(x) == depth.get(y) && parent.get(x) != parent.get(y);
    }
}
Python
class Solution:
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        if not root:
            return False

        queue = deque([root])
        depth = {root.val: 0}
        parent = {root.val: None}

        while queue:
            node = queue.popleft()
            
            if node.left:
                queue.append(node.left)
                depth[node.left.val] = depth[node.val] + 1
                parent[node.left.val] = node
            
            if node.right:
                queue.append(node.right)
                depth[node.right.val] = depth[node.val] + 1
                parent[node.right.val] = node
        
        return (depth[x] == depth[y]) and (parent[x] != parent[y])

Method 2 - DFS with Height and Parent Check in 2 Iterations

Check the height of both the nodes, if heights are different then return false. Check if both the nodes has the same parent, if yes then return false. else return true.

Code

Java
public boolean areCousins(Node root, int x, int y) {
	if (getHeight(root, x, 1) != getHeight(root, y, 1)) {
		return false;
	}

	if (sameParents(root, x, y) == false) {
		return true;
	}

	return false;

}


public int getHeight(Node root, int x, int height) {
	if (root == null) {
		return 0;
	}

	if (root.val == x) {
		return height;
	}

	int level = getHeight(root.left, x, height + 1);

	if (level != 0) {
		return level;
	}

	return getHeight(root.right, x, height + 1);
}


public boolean sameParents(Node root, int x, int y) {
	if (root == null) {
		return false;
	}

	return ((root.left.val == x && root.right.val == y) ||
		(root.left.val == y && root.right.val == x) ||
		sameParents(root.left, x, y) || sameParents(root.right, x, y));
}

Method 3 - DFS with Height and Parent Check in 1 Iteration

Code

Java
static class NodeComparisonResult {
	public int parent1;
	public int depth1;
	public int parent2;
	public int depth2;
}
public boolean isCousins(TreeNode root, int x, int y) {
	NodeComparisonResult res = new NodeComparisonResult();
	inorder(root.left, x, y, 0, root, res);
	inorder(root.right, x, y, 0, root, res);
	if (res.parent1 != res.parent2 && res.depth1 == res.depth2) {
		return true;
	}
	return false;
}

public void inorder(TreeNode node, int x, int y, int depth, TreeNode parent, NodeComparisonResult res) {
	if (node == null)
		return;
	depth = depth + 1;
	inorder(node.left, x, y, depth, node, res);

	if (node.val == x) {
		res.parent1 = parent.val;
		res.depth1 = depth;
		return;
	} else if (node.val == y) {
		res.parent2 = parent.val;
		res.depth2 = depth;
		return;
	}

	inorder(node.right, x, y, depth, node, res);
}