Invert Binary Tree

Invert Binary Tree

1. What is this problem about?

The Invert Binary Tree interview question asks you to create a mirror image of a binary tree. Every left child should become a right child, and every right child should become a left child, recursively throughout the entire structure.

2. Why is this asked in interviews?

Made famous by a viral tweet regarding a Google interview, the Invert Binary Tree coding problem is the quintessential test of recursion. It evaluates whether a candidate can think hierarchically and understand that a operation on a parent must be applied to all descendants. It's a foundational Binary Tree interview pattern.

3. Algorithmic pattern used

This problem can be solved using Depth-First Search (DFS) or Breadth-First Search (BFS).

• Recursive (DFS):
  1. Base case: if root is null, return null.
  2. Swap root.left and root.right.
  3. Recursively call the function on the new left and right children.
• Iterative (BFS): Use a queue to visit every node and swap its children level by level.

4. Example explanation

Tree: 4 is root, 2 is left, 7 is right.

1. Swap 2 and 7. Root 4 now has 7 on the left and 2 on the right.
2. Go to node 7. Its children (if any) are swapped.
3. Go to node 2. Its children (if any) are swapped. Result: A perfectly mirrored tree.

5. Common mistakes candidates make

• Losing a reference: Swapping root.left = invert(root.right) before saving the original root.left in a temporary variable.
• Only swapping the root: Forgetting to recurse, resulting in only the top level being mirrored.
• Recursive depth: Not mentioning that for extremely deep trees, an iterative BFS approach avoids stack overflow.

6. Interview preparation tip

This problem is all about the Post-order vs Pre-order distinction. In this specific case, both work! Whether you swap children before or after recursing doesn't change the final result, but being able to explain why is a great way to show depth.