Cousins in Binary Tree: Checking Depth and Parent with BFS

Given the root of a binary tree with unique values and the values of two different nodes x and y, determine whether the two nodes are cousins.

This is LeetCode 993: Cousins in Binary Tree. Two nodes in a binary tree are cousins if they have the same depth but different parents. In other words, they sit on the same level of the tree, but they do not share a parent node.

The problem

Think of a family tree. Siblings share the same parent. Cousins are in the same generation but belong to different branches of the family. That is exactly what this problem asks you to check. Given two node values x and y, you need to find each node, record its depth and parent, and then compare.

Example: In the tree [1, 2, 3, null, 4, null, 5], node 4 is a child of node 2 at depth 2, and node 5 is a child of node 3 at depth 2. They have the same depth but different parents, so they are cousins.

The brute force approach

One way to solve this is to run DFS twice, once for x and once for y. Each DFS traversal tracks the current depth and the parent of the target node. After both searches, you compare the results.

def isCousins(root, x, y):
    def dfs(node, target, depth, parent):
        if not node:
            return None
        if node.val == target:
            return (depth, parent)
        left = dfs(node.left, target, depth + 1, node.val)
        if left:
            return left
        return dfs(node.right, target, depth + 1, node.val)

    info_x = dfs(root, x, 0, -1)
    info_y = dfs(root, y, 0, -1)
    return info_x[0] == info_y[0] and info_x[1] != info_y[1]

This works, but you traverse the tree twice. You can do it in a single pass.

The key insight

BFS processes nodes level by level, which means every node you dequeue in the same iteration is at the same depth. You do not need to track depth as a separate variable. If you find both x and y in the same level, you know they are at the same depth. Then you just need to confirm they have different parents.

As you enqueue children, you can check whether a parent's left and right children happen to be x and y. If both belong to the same parent, they are siblings, not cousins. If they appear at the same level but from different parents, they are cousins.

Step-by-step walkthrough

The code

from collections import deque

def isCousins(root, x, y):
    queue = deque([(root, None)])
    while queue:
        found_x = None
        found_y = None
        for _ in range(len(queue)):
            node, parent = queue.popleft()
            if node.val == x:
                found_x = parent
            if node.val == y:
                found_y = parent
            if node.left:
                queue.append((node.left, node.val))
            if node.right:
                queue.append((node.right, node.val))
        if found_x and found_y:
            return found_x != found_y
        if found_x or found_y:
            return False
    return False

Here is what each piece does:

• queue = deque([(root, None)]) initializes BFS with the root node and no parent (since the root has no parent).
• The outer while queue loop runs once per level of the tree.
• The inner for _ in range(len(queue)) loop processes exactly the nodes at the current level. This is the standard BFS level-by-level pattern.
• For each node, we check if its value matches x or y. If so, we record the parent.
• After processing a full level, if both x and y were found, we check whether their parents differ. If only one was found, they cannot be cousins because the other must be at a different depth.

Complexity analysis

Time is O(n) for both approaches, where n is the number of nodes. Each node is visited at most once.

Space differs. DFS uses O(h) for the recursion stack, where h is the height of the tree. BFS uses O(w) for the queue, where w is the maximum width of the tree. In the worst case (a complete binary tree), w can be up to n/2, while h is log n. In a skewed tree, h = n but w = 1. The BFS approach has the advantage of stopping early once both nodes are found.

The building blocks

Level-by-level BFS

The core technique here is processing the BFS queue one level at a time. Instead of just popping one node at a time, you snapshot the current queue length and process exactly that many nodes. This gives you implicit depth tracking without needing a depth counter. This pattern shows up in Binary Tree Level Order Traversal, Binary Tree Right Side View, and many other tree problems.

Parent tracking during traversal

When you enqueue a child node, you can attach any metadata you want. Here you attach the parent value. This avoids a second pass or a separate hash map for parent lookups. The same idea applies whenever you need to associate additional context with nodes during BFS or DFS.

Edge cases

• x or y is the root. The root has no parent (parent = None). If the other node is at depth 1, they are at different depths and not cousins. If somehow both were the root, the problem guarantees distinct values, so this will not happen.
• x and y are siblings. They share the same parent. Same depth but same parent means they are not cousins. The algorithm catches this by comparing parents after finding both on the same level.
• x and y are at different depths. If you find one but not the other at a given level, you return false immediately. There is no need to continue searching.
• Tree has only one or two nodes. With fewer than three nodes, there is no way for two distinct nodes to be cousins. The algorithm handles this naturally because it will never find both on the same level with different parents.

From understanding to recall

You just traced through BFS level by level, watching how the algorithm records the parent of each target node and compares them at the end of each level. The pattern is clean: enqueue children with their parent, process a full level, check results.

But will you remember to snapshot the queue length before the inner loop? Will you remember to store the parent in the queue tuple instead of using a separate data structure? Will you recall the early exit when only one of the two targets appears at a level?

Spaced repetition builds that kind of automatic recall. You write the solution from scratch at increasing intervals: after a day, then three days, then a week. Each time, you reconstruct the BFS setup, the level-by-level loop, and the cousin check from memory. After a few rounds, the pattern becomes second nature.

Level-by-level BFS is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Binary Tree Level Order Traversal - The foundational BFS pattern this problem builds on
• Maximum Depth of Binary Tree - A simpler depth-tracking problem using tree traversal
• Symmetric Tree - Another problem that compares nodes at the same level of a tree