Coding Interview PatternsCousins in Binary Tree
EasyTree Breadth-First Search

Cousins in Binary Tree

Explanation & Solution

Practice Problem

Description

Given the root of a binary tree with unique values and two different node values x and y, return true if the nodes corresponding to the values x and y are cousins, or false otherwise.

Two nodes of a binary tree are cousins if they have the same depth but different parents.

Note that in a binary tree, the root node is at depth 0, and children of each depth k node are at depth k + 1.

Examples

Example 1:

```tree

[1, 2, 3, 4]

`

Input:root = [1, 2, 3, 4], x = 4, y = 3
0
1
1
2
2
3
3
4

Output: false

Explanation: Node 4 is at depth 2 with parent 2, and node 3 is at depth 1. They are not at the same depth, so they cannot be cousins.

Example 2:

```tree

[1, 2, 3, null, 4, null, 5]

`

Input:root = [1, 2, 3, null, 4, null, 5], x = 5, y = 4
0
1
1
2
2
3
3
null
4
4
5
null
6
5

Output: true

Explanation: Node 5 has parent 3 and node 4 has parent 2. Both are at depth 2 with different parents, so they are cousins.

Example 3:

```tree

[1, 2, 3, null, 4]

`

Input:root = [1, 2, 3, null, 4], x = 2, y = 3
0
1
1
2
2
3
3
null
4
4

Output: false

Explanation: Node 2 and node 3 are at the same depth but they are siblings (same parent: 1), not cousins. Actually, they share the same parent so they are siblings, not cousins.

Constraints

  • The number of nodes in the tree is in the range [2, 100]
  • 1 <= Node.val <= 100
  • Each node has a unique value
  • x != y
  • x and y exist in the tree

Approach

Tree Breadth-First Search pattern

1. Base Case

  • If root is null:
  • Return false

2. Initialize BFS with Parent Tracking

  • Create a queue with entries of { node, parent }
  • Start with { node: root, parent: null }

3. Process Level by Level

  • While the queue is not empty:
  • Record the levelSize
  • Initialize xParent and yParent to null
  • Loop levelSize times:
  • Dequeue a { node, parent } entry
  • If node.val === x, record its parent as xParent
  • If node.val === y, record its parent as yParent
  • Enqueue children with current node as their parent

4. Check After Each Level

  • Both found (xParent && yParent):
  • Return true if they have different parents (xParent !== yParent)
  • Return false if they share the same parent (they're siblings, not cousins)
  • Only one found (xParent || yParent):
  • Return false — they're at different depths, so they can't be cousins

5. Return False

  • If we exhaust the tree without finding both, return false

Key Insight

  • Cousins must satisfy two conditions: same depth AND different parents
  • BFS naturally groups nodes by depth, so finding both x and y in the same level confirms same depth
  • Tracking parents lets us verify the second condition
Time
O(n)visit each node once
Space
O(n)for the queue

Visualization

Input:
DFS Traversal[1, 2, 3, 4]
1234
output0

Press play to start DFS traversal

CurrentIn stackComplete
9 steps

Solution Code

Previous
Symmetric Tree
Next
N-ary Tree Level Order Traversal