Problem Description

You are given a binary tree with unique node values and two values x and y that exist in the tree. Your task is to determine if the nodes containing these values are cousins.

Two nodes are considered cousins if they meet both of these conditions:

1. They are at the same depth in the tree
2. They have different parents

The depth of a node is defined as:

• The root node is at depth 0
• Children of a node at depth k are at depth k + 1

The solution uses a breadth-first search (BFS) approach with a queue to traverse the tree level by level. For each node visited, it tracks both the node and its parent. The algorithm:

1. Starts with the root node (which has no parent) in the queue
2. Processes each level of the tree completely before moving to the next level
3. When it finds node x, it records its parent (p1) and depth (d1)
4. When it finds node y, it records its parent (p2) and depth (d2)
5. For each node processed, adds its children to the queue along with the current node as their parent
6. After traversing the entire tree, checks if x and y have different parents (p1 != p2) and the same depth (d1 == d2)

The function returns true if the nodes are cousins (same depth, different parents), and false otherwise.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph with nodes (tree nodes) and edges (parent-child relationships).

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure.

DFS

• Yes: We arrive at DFS as our algorithm choice for this tree problem.

Conclusion: The flowchart suggests using a DFS (Depth-First Search) approach for solving the Cousins in Binary Tree problem.

Why DFS Works Here

DFS is particularly suitable for this problem because:

1. Tree Traversal: We need to traverse the entire tree to find both nodes x and y
2. Parent Tracking: During DFS traversal, we can naturally track the parent of each node as we recursively explore
3. Depth Tracking: The recursive call stack in DFS inherently tracks the depth - each recursive call represents going one level deeper

Alternative DFS Implementation

While the provided solution uses BFS, a DFS approach would work equally well:

def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
    def dfs(node, parent, depth, target):
        if not node:
            return None, None
        if node.val == target:
            return parent, depth
      
        left_result = dfs(node.left, node, depth + 1, target)
        if left_result[0] is not None:
            return left_result
          
        return dfs(node.right, node, depth + 1, target)
  
    x_parent, x_depth = dfs(root, None, 0, x)
    y_parent, y_depth = dfs(root, None, 0, y)
  
    return x_parent != y_parent and x_depth == y_depth

Both DFS and BFS are valid approaches for this tree traversal problem, with the flowchart correctly identifying DFS as a suitable pattern for tree-based problems.

Intuition

To determine if two nodes are cousins, we need to check two things: whether they're at the same depth and whether they have different parents. This immediately tells us we need to track both the depth and parent information for each node as we traverse the tree.

Think about how you would manually check if two people are cousins in a family tree - you'd trace back to see if they're at the same generation level (depth) and confirm they have different immediate parents. The same logic applies here.

The key insight is that we need to explore the tree systematically to find both target nodes while keeping track of their relationships. When we visit each node, we need to remember:

• Who is its parent? (to check if they have different parents)
• How deep is it in the tree? (to check if they're at the same level)

Whether we use BFS or DFS, the core idea remains the same: traverse the tree while maintaining parent-child relationships. BFS naturally processes nodes level by level, making depth tracking straightforward with a depth counter. DFS uses the recursive call stack where each recursive level represents one step deeper into the tree.

The solution becomes clear: find both nodes x and y in the tree, record their parents and depths, then check if they satisfy the cousin criteria: same depth AND different parents. If we find that x and y have the same parent, they're siblings, not cousins. If they're at different depths, they're not cousins either. Only when both conditions are met (same depth, different parents) do we return true.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Solution Approach

The implementation uses a Breadth-First Search (BFS) approach with a queue to traverse the tree level by level. Here's how the solution works:

Data Structures Used:

• A deque (double-ended queue) to store tuples of (node, parent) pairs
• Variables to track parents (p1, p2) and depths (d1, d2) of nodes x and y

Algorithm Steps:

1. Initialize the queue with the root node and None as its parent: q = deque([(root, None)])

2. Set up tracking variables:

   • depth = 0 to track the current level
   • p1, p2 = None, None to store parents of x and y
   • d1, d2 = None, None to store depths of x and y

3. Process nodes level by level:

   while q:
       for _ in range(len(q)):  # Process all nodes at current level

   The inner loop ensures we process all nodes at the same depth before incrementing the depth counter.

4. For each node, check if it matches our targets:

   node, parent = q.popleft()
   if node.val == x:
       p1, d1 = parent, depth
   elif node.val == y:
       p2, d2 = parent, depth

   When we find either target value, we record its parent and current depth.

5. Add children to the queue for next level:

   if node.left:
       q.append((node.left, node))
   if node.right:
       q.append((node.right, node))

   Each child is added with the current node as its parent.

6. Increment depth after processing each level: depth += 1

7. Return the result:

   return p1 != p2 and d1 == d2

   Returns True only if both conditions are met:

   • Different parents (p1 != p2)
   • Same depth (d1 == d2)

Time Complexity: O(n) where n is the number of nodes, as we visit each node once.

Space Complexity: O(w) where w is the maximum width of the tree, which is the maximum number of nodes at any level (worst case O(n/2) for a complete binary tree).

Example Walkthrough

Let's walk through a concrete example to illustrate how the BFS solution finds cousin nodes.

Consider this binary tree where we want to check if nodes with values 4 and 3 are cousins:

        1
       / \
      2   3
     /
    4

Initial Setup:

• Target values: x = 4, y = 3
• Queue starts with: [(1, None)]
• depth = 0, p1 = None, p2 = None, d1 = None, d2 = None

Level 0 (Root):

• Process node 1 with parent None
• Check: 1 ≠ 4 and 1 ≠ 3, so no match
• Add children to queue: [(2, 1), (3, 1)]
• Increment depth = 1

Level 1:

• Process node 2 with parent 1

  • Check: 2 ≠ 4 and 2 ≠ 3, no match
  • Add left child: queue becomes [(3, 1), (4, 2)]

• Process node 3 with parent 1

  • Check: 3 = y! Record p2 = 1, d2 = 1
  • No children to add

• After processing level 1, increment depth = 2

Level 2:

• Process node 4 with parent 2
  • Check: 4 = x! Record p1 = 2, d1 = 2
  • No children to add
• Queue is now empty

Final Check:

• p1 = 2, p2 = 1 (different parents ✓)
• d1 = 2, d2 = 1 (different depths ✗)
• Return False - they are NOT cousins

Let's try another example where nodes ARE cousins:

        1
       / \
      2   3
     / \   \
    4   5   6

Checking if 4 and 6 are cousins:

Level 0: Process node 1, add children 2 and 3

Level 1: Process nodes 2 and 3, add their children 4, 5, and 6

Level 2:

• Find node 4 with parent 2 at depth 2
• Find node 6 with parent 3 at depth 2

Result:

• Different parents (2 ≠ 3) ✓
• Same depth (2 = 2) ✓
• Return True - they ARE cousins!

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of nodes in the binary tree.

The algorithm uses BFS (Breadth-First Search) to traverse the tree level by level. Each node in the tree is visited exactly once - we add it to the queue once and process it once when we pop it from the queue. For each node, we perform constant time operations: checking if its value equals x or y, and adding its children to the queue. Therefore, the overall time complexity is linear with respect to the number of nodes.

Space Complexity: O(w) where w is the maximum width of the tree.

The space complexity is determined by the maximum size of the queue at any point during the traversal. In BFS, the queue stores all nodes at the current level being processed. The maximum number of nodes at any level is the width of the tree. In the worst case (a complete binary tree), the maximum width occurs at the last level and can be up to n/2 nodes, making the space complexity O(n) in the worst case. In the best case (a skewed tree), the width is 1, making the space complexity O(1). Generally, we express this as O(w) where w represents the maximum width of the tree.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Early Termination Optimization Gone Wrong

A common pitfall is trying to optimize by returning early once both x and y are found at the same level:

Incorrect Approach:

while queue:
    level_size = len(queue)
    found_x = found_y = False
    parent_x = parent_y = None
  
    for _ in range(level_size):
        node, parent = queue.popleft()
      
        if node.val == x:
            found_x = True
            parent_x = parent
        elif node.val == y:
            found_y = True
            parent_y = parent
      
        # Early termination - WRONG!
        if found_x and found_y:
            return parent_x != parent_y
          
        if node.left:
            queue.append((node.left, node))
        if node.right:
            queue.append((node.right, node))

Why it fails: This breaks the level-order traversal by returning before processing all nodes at the current level. You might miss adding children to the queue, and the check happens before the level is fully processed.

Correct Approach: Check after processing the entire level:

while queue:
    level_size = len(queue)
    found_x = found_y = False
    parent_x = parent_y = None
  
    for _ in range(level_size):
        node, parent = queue.popleft()
      
        if node.val == x:
            found_x = True
            parent_x = parent
        elif node.val == y:
            found_y = True
            parent_y = parent
          
        if node.left:
            queue.append((node.left, node))
        if node.right:
            queue.append((node.right, node))
  
    # Check after the entire level is processed
    if found_x and found_y:
        return parent_x != parent_y
  
    # If only one is found at this level, they can't be cousins
    if found_x or found_y:
        return False

2. Parent-Child Confusion

Another pitfall is checking if x and y are parent and child of each other, thinking this automatically means they're not cousins:

Incorrect Additional Check:

# Trying to handle parent-child case explicitly - UNNECESSARY!
if node.val == x:
    if node.left and node.left.val == y:
        return False
    if node.right and node.right.val == y:
        return False

Why it's unnecessary: The BFS approach already handles this correctly. If x is the parent of y, they will be at different depths, so depth_x != depth_y will make the function return False.

3. Using Node References Instead of Values

A subtle mistake is storing node references instead of parent references:

Incorrect:

if node.val == x:
    parent_x = node  # WRONG - storing the node itself
    depth_x = current_depth

Correct:

if node.val == x:
    parent_x = parent  # Correct - storing the parent reference
    depth_x = current_depth

This would cause incorrect comparisons since you'd be comparing the nodes themselves rather than their parents.