Cousins in Binary Tree: Same Level, Different Parents

This one is a Easy-rated classic reported from Meta, Amazon, Google interviews: "Cousins in Binary Tree". Like every post in this series, the goal is not memorizing the answer — it is recognizing the Tree BFS pattern on sight. Part 8 of 11 in the Tree BFS arc.

The Problem

Two nodes are cousins if they share a depth but have different parents. Given a tree with unique values and two target values x and y, return whether they are cousins. Small question, but it cleanly tests carrying metadata through a BFS — a skill the harder graph problems assume.

Input:  root = [1, 2, 3, None, 4, None, 5], x = 5, y = 4
Output: True
Both sit at depth 2 with parents 3 and 2.

Recognizing the Tree BFS Pattern

Breadth-first search explores a tree or graph level by level using a queue, and its defining superpower is the level snapshot: freeze the queue length, process exactly that many nodes, and you have processed one complete level. Anything phrased per-level — level lists, level averages, rightmost visible node, shortest path in unweighted structures — is BFS by construction.

The question is two lookups — depth of v, parent of v — and BFS naturally produces both if you enqueue (node, parent) and process by level. Alternatively, the sibling check can be done at enqueue time: if x and y are children of the same node, fail fast.

The Approach

Level-snapshot BFS storing (node, parent). Within each level, record whether x and y appear and with which parents. If both appear in the same level with different parents, True; if exactly one appears in a level, False — depths differ; the same-parent case is False by definition.

Checking level-locally avoids a full depth map — the loop exits at the first level containing either target.

Python Solution

class TreeNode:
    def __init__(self, val: int = 0, left: "TreeNode | None" = None,
                 right: "TreeNode | None" = None):
        self.val = val
        self.left = left
        self.right = right


from collections import deque


def is_cousins(root: TreeNode | None, x: int, y: int) -> bool:
    """True if x and y share depth but not parents."""
    if not root:
        return False
    queue: deque[tuple[TreeNode, TreeNode | None]] = deque([(root, None)])
    while queue:
        found: dict[int, TreeNode | None] = {}
        for _ in range(len(queue)):
            node, parent = queue.popleft()
            if node.val in (x, y):
                found[node.val] = parent
            if node.left:
                queue.append((node.left, node))
            if node.right:
                queue.append((node.right, node))
        if len(found) == 2:
            return found[x] is not found[y]
        if len(found) == 1:
            return False                   # depths differ
    return False

Complexity

• Time: O(n) — at most one full traversal, early exit at the first relevant level
• Space: O(w) — queue of node-parent pairs

Interview Tips and Follow-Ups

• Compare parents by identity (is not), not value — parent nodes, not parent values, define cousinhood when values could repeat.
• The one-found-in-a-level early False is a small optimization interviewers like hearing justified: the other target must be deeper.
• Generalization: k-th cousins (same depth, parents differing at the k-th ancestor) — LCA machinery, a bridge to the DFS arc.

That wraps part 8 of the Tree BFS arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.