LeetCode 993: Cousins in Binary Tree

Problem Restatement

We are given the root of a binary tree with unique values.

We are also given two different values:

x
y

Both values exist in the tree.

We need to return True if the nodes with values x and y are cousins.

Two nodes are cousins if:

The root has depth 0. Children of a node at depth d have depth d + 1.

Input and Output

Function shape:

def isCousins(root: Optional[TreeNode], x: int, y: int) -> bool:
    ...

Examples

Example 1:

root = [1, 2, 3, 4]
x = 4
y = 3

Tree:

      1
     / \
    2   3
   /
  4

Node 4 has depth 2.

Node 3 has depth 1.

They are not at the same depth.

Answer:

False

Example 2:

root = [1, 2, 3, None, 4, None, 5]
x = 5
y = 4

Tree:

      1
     / \
    2   3
     \   \
      4   5

Node 4 and node 5 are both at depth 2.

Their parents are different: 2 and 3.

Answer:

True

Example 3:

root = [1, 2, 3, None, 4]
x = 2
y = 3

Node 2 and node 3 are at the same depth, but they have the same parent: node 1.

They are siblings, not cousins.

Answer:

False

First Thought: Find Depth and Parent

To decide whether two nodes are cousins, we need two pieces of information for each target node:

After finding both nodes:

same_depth = depth_x == depth_y
different_parent = parent_x != parent_y

The answer is:

same_depth and different_parent

We can collect this information with either DFS or BFS.

Key Insight

BFS is natural because it processes the tree level by level.

At each level:

1. Check whether x appears.
2. Check whether y appears.
3. Record their parents.
4. After finishing the level, decide whether they are cousins.

If both are found in the same level, they have the same depth. Then they are cousins only if their parents are different.

If only one is found in a level, the other one must be at a different depth, so they cannot be cousins.

Algorithm

Use a queue containing pairs:

(node, parent)

Start with:

(root, None)

While the queue is not empty:

1. Process exactly one level.
2. Set parent_x = None and parent_y = None.
3. For each node in the current level:
   • If node.val == x, store its parent.
   • If node.val == y, store its parent.
   • Push children into the queue with the current node as parent.
4. After the level:
   • If both parents were found, return whether they are different.
   • If exactly one was found, return False.

If the loop ends, return False.

Correctness

BFS processes all nodes at depth d before any node at depth d + 1.

During each level, the algorithm records the parent of x if x appears at that depth, and the parent of y if y appears at that depth.

If both are found during the same level, then they have the same depth. They are cousins exactly when their recorded parents are different, so returning that comparison is correct.

If only one target is found during a level, then the other target cannot be at that same depth. Since BFS will only move deeper afterward, the two nodes have different depths. They cannot be cousins, so returning False is correct.

Because both target values exist and BFS eventually visits every node, the algorithm correctly determines whether the two target nodes are cousins.

Complexity

Let n be the number of nodes and w be the maximum width of the tree.

In the worst case, w can be O(n).

Implementation

from collections import deque

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
        queue = deque([(root, None)])

        while queue:
            level_size = len(queue)
            parent_x = None
            parent_y = None

            for _ in range(level_size):
                node, parent = queue.popleft()

                if node.val == x:
                    parent_x = parent

                if node.val == y:
                    parent_y = parent

                if node.left:
                    queue.append((node.left, node))

                if node.right:
                    queue.append((node.right, node))

            if parent_x is not None and parent_y is not None:
                return parent_x != parent_y

            if parent_x is not None or parent_y is not None:
                return False

        return False

Code Explanation

The queue stores each node together with its parent:

queue = deque([(root, None)])

For each loop iteration, we process one full depth level:

level_size = len(queue)

At the start of each level, we have not found either target:

parent_x = None
parent_y = None

When a target appears, store its parent:

if node.val == x:
    parent_x = parent

if node.val == y:
    parent_y = parent

Children are pushed with the current node as their parent:

if node.left:
    queue.append((node.left, node))

if node.right:
    queue.append((node.right, node))

After finishing the level, if both targets were found, they have the same depth:

if parent_x is not None and parent_y is not None:
    return parent_x != parent_y

If only one target was found, they are at different depths:

if parent_x is not None or parent_y is not None:
    return False

Testing

from collections import deque
from typing import Optional

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

def run_tests():
    s = Solution()

    root1 = TreeNode(
        1,
        TreeNode(2, TreeNode(4)),
        TreeNode(3),
    )
    assert s.isCousins(root1, 4, 3) is False

    root2 = TreeNode(
        1,
        TreeNode(2, None, TreeNode(4)),
        TreeNode(3, None, TreeNode(5)),
    )
    assert s.isCousins(root2, 5, 4) is True

    root3 = TreeNode(
        1,
        TreeNode(2, None, TreeNode(4)),
        TreeNode(3),
    )
    assert s.isCousins(root3, 2, 3) is False

    root4 = TreeNode(
        1,
        TreeNode(2, TreeNode(4), TreeNode(5)),
        TreeNode(3),
    )
    assert s.isCousins(root4, 4, 5) is False

    print("all tests passed")

run_tests()