Correct a Binary Tree

Correct a Binary Tree

What is this problem about?

In the Correct a Binary Tree interview question, you are given the root of a binary tree that has exactly one "wrong" node. This invalid node has a right child that points to another node at the same depth but to its right, which violates the standard tree structure (it creates a cycle-like link within a level). Your task is to find this invalid node, remove it and its entire subtree, and return the corrected tree's root.

Why is this asked in interviews?

Google uses the Correct a Binary Tree coding problem to test a candidate's ability to navigate trees and handle unexpected structure violations. It evaluates your understanding of tree traversals—specifically, how to detect a "horizontal" link that shouldn't exist. It requires a solid grasp of how to update parent pointers during a traversal to effectively "prune" a branch of the tree.

Algorithmic pattern used

The most effective Tree interview pattern for this is Breadth-First Search (BFS) or Depth-First Search (DFS) with a Right-to-Left order.

1. Perform a traversal where you visit the right child before the left child.
2. Use a Hash Set to keep track of all visited nodes.
3. If you encounter a node whose right child is already in the Hash Set, that node is the "invalid" one.
4. Remove the invalid node by returning null to its parent during the recursive cleanup.

Example explanation

Imagine a tree where:

• Root 1 has children 2 (left) and 3 (right).
• 2 has children 4 (left) and 5 (right).
• 3 has a right child 6.
• Violation: The right child of 5 points to 6 (its "cousin" at the same depth). By traversing Right-to-Left:

1. Visit 1, then 3, then 6. Add {1, 3, 6} to visited.
2. Visit 2, then 5.
3. Check 5's right child: it's 6, which is already in the set!
4. Node 5 is invalid. Remove it from 2.

Common mistakes candidates make

• Wrong Traversal Order: Using a standard Left-to-Right traversal, which makes it harder to detect the "right-pointing" invalid node.
• Incomplete Pruning: Only removing the link to the invalid node but not properly restructuring the parent's child pointer.
• Missing the Depth Factor: Forgetting that the invalid link always points to a node at the same depth.

Interview preparation tip

When a tree problem mentions "nodes at the same level," always consider if a Level-Order Traversal (BFS) or a specific DFS order (like Right-to-Left) simplifies the logic.