Cousins in Binary Tree

Cousins in Binary Tree

What is this problem about?

In the Cousins in Binary Tree interview question, you are given the root of a binary tree and two node values $x$ and $y$. Two nodes are considered "cousins" if they satisfy two conditions:

1. They are at the same depth in the tree.
2. They have different parents. You need to return true if $x$ and $y$ are cousins, and false otherwise.

Why is this asked in interviews?

Microsoft and Amazon use the Cousins in Binary Tree coding problem to assess a candidate's ability to track multiple pieces of information (depth and parent) during a tree traversal. It’s an "Easy" difficulty problem that evaluates whether you can use Breadth-First Search (BFS) or Depth-First Search (DFS) to capture and compare node metadata.

Algorithmic pattern used

This problem follows a Tree Traversal pattern.

• BFS (Level Order): Traverse the tree level by level. If you find both $x$ and $y$ at the same level, check if they share the same parent. Using a queue to store (node, parent) pairs is a common implementation.
• DFS (Recursive): Traverse the tree and store the (depth, parent) for both $x$ and $y$ in variables or a map. After the traversal, compare the stored values.

Example explanation

Imagine a tree: 1 / 2 3 /
4 5 Target nodes: 4 and 5.

1. Root 1: depth 0.
2. Node 2 and 3: depth 1.
3. Node 4 (child of 2): depth 2.
4. Node 5 (child of 3): depth 2. Since 4 and 5 are at the same depth (2) but have different parents (2 and 3), they are cousins. Returns true.

Common mistakes candidates make

• Same Parent Check: Forgetting to check that the parents are different. Siblings (same depth, same parent) are NOT cousins.
• Early Exit: Returning false as soon as you find $x$ at one depth, without checking where $y$ is.
• Null Pointers: Not handling nodes with only one child or no children during the parent lookup.

Interview preparation tip

BFS is often the most natural choice for "same depth" problems because it naturally groups nodes by level. If you use DFS, remember to pass both the current depth and the parent node as arguments in the recursive calls.