Cousins in Binary Tree

Adobe Interview Question

Problem Overview

Difficulty: Easy
LeetCode Pattern: BFS

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

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

Tree:
    1
   / \
  2   3
 /     \
4       5

Example 1:
· Input: x = 4, y = 5
· Output: true
· Reason: same depth, different parent

Example 2:
· Input: x = 2, y = 3
· Output: false
· Reason: same depth, same parent

---

Step 1: Clarify Requirements

• Can the tree be empty?

  • Yes, it can be empty.

  • Return false in that case.

• Can x and y be the same?

  • No, all values are unique.

• What if a given node doesn’t exist?

  • Return false in this case.

---

Step 2: Discuss Approaches

1/ Use DFS Calls (Suboptimal ⚠️)

• Logic:

  • Use DFS to find:

    • the depth of x

    • the parent of x

  • Use DFS to find:

    • the depth of y

    • the parent of y

  • Check:

    • depth_x == depth_y

    • parent_x != parent_y

• Big O:

  • Time Complexity: O(n)

  • Space Complexity: O(h)

---

2/ Use BFS (Optimal ✅)

• Logic:

  • Use BFS (queue)

  • Traverse tree level by level

  • For each level:

    • Track if x or y is found

    • If only one found:

      • return false

    • If both found:

      • return parent_x != parent_y

  • Return false if tree ends

• Big O:

  • Time Complexity: O(n)

  • Space Complexity: O(n)

---

Step 3: Write Code (Optimal)

Python

---

Java

---

C++

---

Step 4: Answer Follow-Ups

• What if the tree is empty?

  • Return false.

• What if tree is very deep?

  • DFS can cause stack overflow.

  • Using BFS is a better choice.

• How to check this for multiple pairs?

  • Modify existing solution.

  • At each level, check for all pairs.