Cousins in Binary Tree (LeetCode 993)

The problem

You get the root of a binary tree with unique values, and two different values x and y that are both in the tree. Two nodes are cousins if they are at the same depth but have different parents. Return True if the nodes holding x and y are cousins.

Input:      1
           / \
          2   3
           \   \
            4   5
        x = 4, y = 5

Output: True

4 and 5 are both at depth 2, and their parents are 2 and 3, which differ.

How to think about it

Start with the definition. “Cousins” is two conditions: same depth and different parent. Siblings (same parent) are at the same depth but don’t count. So for each of x and y, all you need is two facts: its parent and its depth. Once you have them, the answer is one comparison.

Brute force would overthink it. You could compute the full path from the root to each node and compare path lengths and the second-last elements. It works, but you store whole paths for nothing.

The key insight: one traversal that carries (parent, depth) down with it. When you go from a node to its child, the child’s parent is the current node and its depth is one more. When you reach the target value, return the pair. This is a small DFS helper, called once for x and once for y.

Why it sits in the BFS lesson. It’s a level question. A BFS version processes one level at a time and checks whether x and y both appear on the same level with different parents. Both are O(n). The DFS helper here is shorter to write, and it is what the tested source uses.

The tell is “same level/depth” combined with “relationship between two specific nodes”: collect depth and parent for each, then compare.

Approach

1. Write info(node, parent, depth, target):
   • return None if node is None,
   • return (parent, depth) if node.val == target,
   • otherwise search the left subtree, then the right, with depth + 1 and node.val as the parent.
2. Get (px, dx) for x and (py, dy) for y.
3. Return dx == dy and px != py.

Solution

def is_cousins(root, x, y):
    def info(node, parent, depth, target):        # returns (parent value, depth) of target
        if not node: return None
        if node.val == target: return (parent, depth)
        return info(node.left, node.val, depth + 1, target) or \
               info(node.right, node.val, depth + 1, target)
    px, dx = info(root, None, 0, x)
    py, dy = info(root, None, 0, y)
    return dx == dy and px != py                  # same depth, different parent
# is_cousins([1,2,3,null,4,null,5], 4, 5) -> True

The or works because a found result is a non-empty tuple, which is truthy even when it is (None, 0).

Dry run

On the example, the search for x = 4 and then y = 5:

Complexity

• Time: O(n). Each search visits each node at most once, and there are two searches.
• Space: O(h), the recursion depth, where h is the tree height: O(log n) if balanced, O(n) if it’s a chain.

Edge cases and pitfalls

• Siblings: is_cousins([1,2,3], 2, 3) is False; same depth, same parent.
• One of them is the root: the root has depth 0 and no other node does, so the answer is False.
• Different depths: False, even if the parents differ.
• Comparing parent values is safe only because values are unique. If they weren’t, compare parent nodes instead.
• Returning early in BFS when only one is found. If a level holds x but not y, the answer is already False; don’t keep searching deeper.

Related problems

• Binary Tree Level Order Traversal (LeetCode 102): the level-by-level loop the BFS version of this uses.
• Lowest Common Ancestor of a Binary Tree (LeetCode 236): another question about how two nodes relate in a tree.
• Maximum Depth of Binary Tree (LeetCode 104): passing depth down a recursive traversal.