Cousins in Binary Tree — LC 993 BFS Depth and Parent Check

Problem Statement#

LeetCode 993 — Cousins in Binary Tree | Difficulty: Easy

Given the root of a binary tree and two integers x and y, return true if the nodes with values x and y are cousins. Two nodes are cousins if they are at the same depth with different parents.

Constraints:

• The number of nodes is in the range [2, 100]
• 1 <= Node.val <= 100
• Each node has a unique value
• x != y

Input:  root = [1,2,3,4], x = 4, y = 3
Output: false
Explanation: 4 is at depth 2 (parent 2), 3 is at depth 1 (parent 1). Different depths.

Input:  root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true
Explanation: Both 5 and 4 are at depth 2 with different parents (3 and 2 respectively).

Why This Problem Matters#

Cousins in Binary Tree is an Amazon and Microsoft interview problem that tests clean BFS level-order traversal with per-node metadata tracking. While it is an easy problem, the implementation reveals whether you can track parent and depth simultaneously in a single BFS pass without extra data structures.

The problem also distinguishes between siblings (same parent) and cousins (same depth, different parents) — a distinction that tests whether candidates read problem statements carefully. Many candidates accidentally return true for siblings.

The Core Insight#

Two nodes are cousins if and only if:

1. They are at the same depth (same BFS level)
2. They have different parents

BFS processes nodes level by level. For each level, record the parent of any node that matches x or y. After processing a complete level, if both x and y were found, check whether their parents are the same (siblings, return false) or different (cousins, return true).

If only one was found at a level, they are at different depths — return false immediately.

Visual Dry Run#

Tree: [1, 2, 3, null, 4, null, 5], x=5, y=4

BFS level by level:

Both found at level 2, parents are different (3 != 2) → return true.

Solution (Optimal)#

from collections import deque
 
class Solution:
    def isCousins(self, root, x: int, y: int) -> bool:
        # BFS: store (node, parent_value) pairs
        queue = deque([(root, None)])
 
        while queue:
            x_parent = None
            y_parent = None
 
            # Process entire level at once
            for _ in range(len(queue)):
                node, parent = queue.popleft()
 
                if node.val == x:
                    x_parent = parent
                if node.val == y:
                    y_parent = parent
 
                if node.left:
                    queue.append((node.left, node.val))
                if node.right:
                    queue.append((node.right, node.val))
 
            # Both found at this level: cousins if different parents
            if x_parent is not None and y_parent is not None:
                return x_parent != y_parent
 
            # Only one found: different depths, not cousins
            if x_parent is not None or y_parent is not None:
                return False
 
        return False

var isCousins = function(root, x, y) {
    let queue = [[root, null]];
 
    while (queue.length) {
        let xParent, yParent;
        const next = [];
 
        for (const [node, parent] of queue) {
            if (node.val === x) xParent = parent;
            if (node.val === y) yParent = parent;
 
            if (node.left) next.push([node.left, node.val]);
            if (node.right) next.push([node.right, node.val]);
        }
 
        // Both found at this level
        if (xParent !== undefined && yParent !== undefined) {
            return xParent !== yParent;
        }
 
        // Only one found — different depths
        if (xParent !== undefined || yParent !== undefined) {
            return false;
        }
 
        queue = next;
    }
 
    return false;
};

Time: O(n) — BFS visits every node at most once Space: O(n) — queue holds at most one full level of nodes

Common Mistakes#

• Returning true when both nodes are siblings (same parent) — cousins require different parents
• Not checking if only one was found at a level — if one is found and the other is not, they are at different depths
• Using depth tracking with a separate depth variable instead of level-by-level BFS — the level-by-level approach naturally handles both conditions at once
• Storing node references as parents instead of values — for this problem, comparing parent values is sufficient

Interview Tips#

• State both conditions explicitly before coding: same depth AND different parents
• Show that the early return (if only one found, return false) is important for correctness
• The BFS level-by-level processing with for _ in range(len(queue)) is a clean pattern worth explaining
• DFS is also valid — track (depth, parent) during DFS and compare after finding both nodes

Follow-up Questions#

• How would you find all groups of cousins (all nodes at the same level with different parents)? BFS level by level, group siblings together, return all non-sibling pairs per level.
• How would you solve this with DFS? Store (depth, parent) for x and y as you traverse; compare after the DFS completes.
• What if x or y doesn't exist in the tree? The problem guarantees both exist. If not, handle by checking if x_parent or y_parent was ever set.
• LC 1993 (Operations on Tree) extends this concept — cousins become relevant in tree-structured permission systems.

Key Takeaways#

• Cousins require exactly two conditions: same depth AND different parents
• BFS processes one level at a time — check both conditions at the end of each level
• If both x and y are found at the same level, return x_parent != y_parent
• If only one is found at a level, return false immediately — they are at different depths
• Time O(n), space O(n) — BFS visits each node once; queue holds at most one level
• The early return for "only one found" is essential — without it, the algorithm could incorrectly continue
• DFS alternative: store depth and parent for each target node during traversal, compare at the end