Problem Statement

Given the root of a binary tree with unique values and two different nodes x and y, return a boolean value based on whether the nodes corresponding to the values x and y are cousins.

Two nodes are cousins if they are at the same depth but have different parents.

Examples

Example 1:

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

    1
   / \
  2   3
 /   / \
4   5   6  

• Expected Output: true
• Justification: Nodes 4 and 5 both are at depth 2 with parent 2. They are cousins because their parents are different and they are at the same depth.

Example 2:

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

    1
   / \
  2   3
 / \  
4   5   
   / \
  6   7

• Expected Output: false
• Justification: Both nodes 6 and 7 are at depth 3, but they have the same parent 5.

Example 3:

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

    1
  /  \
 2    3
  \   /
   4 5

• Expected Output: true
• Justification: Node 4 is at depth 2 with parent 2. Node 5 is at depth 2 with parent 3. Both nodes are at the same depth but have different parents.

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 are exist in the tree.

Solution

To solve this problem, we need to traverse the binary tree to find the depth and parent of each node. We can use a Breadth-First Search (BFS) approach to ensure we explore each level of the tree fully before moving on to the next. This will help us easily determine the depth of each node. During this traversal, we will keep track of the parent of each node. Once we have this information, we can check if the nodes x and y are at the same depth and have different parents.

This approach is effective because it ensures that we traverse each node only once, making it time-efficient. Additionally, using BFS allows us to process nodes level by level, which is helpful for maintaining the depth information. This method leverages the structure of the binary tree efficiently and ensures that we meet the problem's requirements without unnecessary complexity.

Step-by-Step Algorithm

1. Initialize Data Structures:

   • Create a map to store depth and parent information for each node.
   • Create a queue to perform BFS. Initially, add the root node to the queue with depth 0 and no parent.

2. Perform BFS Traversal:

   • While the queue is not empty, do the following:
     • Dequeue the front element from the queue.
     • If the current node has a left child:
       • Enqueue the left child with an incremented depth and the current node as its parent.
       • Store the left child's depth and parent in the map.
     • If the current node has a right child:
       • Enqueue the right child with an incremented depth and the current node as its parent.
       • Store the right child's depth and parent in the map.

3. Check Cousin Condition:

   • Retrieve the depth and parent information of nodes x and y from the map.
   • Return true if the depths of x and y are the same and their parents are different. Otherwise, return false.

Algorithm Walkthrough

Given input: [1, 2, 3, 4, null, 5, 6], x = 4, y = 5

Initialization:

• Map to store depth and parent information.
• Queue for BFS, starting with the root node:
  • Queue: [(1, 0, None)]

Step 1: Process the root node (1)

• Dequeue (1, 0, None):
  • Current node: 1
  • Depth: 0
  • Parent: None
• Enqueue its children (2 and 3):
  • Queue: [(2, 1, 1), (3, 1, 1)]
• Update the map:
  • Map: {1: (0, None)}

Step 2: Process node (2)

• Dequeue (2, 1, 1):
  • Current node: 2
  • Depth: 1
  • Parent: 1
• Enqueue its left child (4):
  • Queue: [(3, 1, 1), (4, 2, 2)]
• Update the map:
  • Map: {1: (0, None), 2: (1, 1)}

Step 3: Process node (3)

• Dequeue (3, 1, 1):
  • Current node: 3
  • Depth: 1
  • Parent: 1
• Enqueue its children (5 and 6):
  • Queue: [(4, 2, 2), (5, 2, 3), (6, 2, 3)]
• Update the map:
  • Map: {1: (0, None), 2: (1, 1), 3: (1, 1)}

Step 4: Process node (4)

• Dequeue (4, 2, 2):
  • Current node: 4
  • Depth: 2
  • Parent: 2
• Node 4 has no children, so nothing is added to the queue.
• Update the map:
  • Map: {1: (0, None), 2: (1, 1), 3: (1, 1), 4: (2, 2)}

Step 5: Process node (5)

• Dequeue (5, 2, 3):
  • Current node: 5
  • Depth: 2
  • Parent: 3
• Node 5 has no children, so nothing is added to the queue.
• Update the map:
  • Map: {1: (0, None), 2: (1, 1), 3: (1, 1), 4: (2, 2), 5: (2, 3)}

Step 6: Process node (6)

• Dequeue (6, 2, 3):
  • Current node: 6
  • Depth: 2
  • Parent: 3
• Node 6 has no children, so nothing is added to the queue.
• Update the map:
  • Map: {1: (0, None), 2: (1, 1), 3: (1, 1), 4: (2, 2), 5: (2, 3), 6: (2, 3)}

Check Cousin Condition

• Retrieve the information of nodes 4 and 5:
  • Node 4: Depth = 2, Parent = 2
  • Node 5: Depth = 2, Parent = 3
• Since the depths are the same and the parents are different, return true.

Code