Change the Root of a Binary Tree

Change the Root of a Binary Tree

What is this problem about?

The "Change the Root of a Binary Tree interview question" is a structural manipulation challenge. You are given a binary tree and a specific leaf node. You need to "reroot" the tree such that the provided leaf becomes the new root. This involves reversing the parent-child relationships along the path from the original root to the new root. Every node on this path must have its old parent as its new child.

Why is this asked in interviews?

Google asks the "Change the Root of a Binary Tree coding problem" to test a candidate's ability to manipulate complex pointer-based data structures. It evaluates whether you can perform non-trivial transformations on a tree without losing nodes or creating cycles. It requires a deep understanding of "Depth-First Search" and the ability to reason about bidirectional relationships in a tree.

Algorithmic pattern used

This problem uses the Path Reversal and DFS patterns.

1. Find the Path: Use DFS to find the path from the current root to the target leaf node.
2. Reverse Relationships: Iterate through the nodes on this path (starting from the leaf and moving up to the original root).
   • For each node curr, make its old parent its new child.
   • Update the old parent's child pointers (remove the reference to curr).
3. Handle Degree: Since it's a binary tree, you must ensure each node still has at most two children. If a node already has a left child, the old parent might need to become the right child.

Example explanation

Original: 1 -> 2, 2 -> 3 (1 is root, 3 is leaf). Path: 1 -> 2 -> 3.

1. Move to 3: New root is 3. Its new child is 2. (3's old parent was 2).
2. Move to 2: 2's new child is 1. (2's old parent was 1).
3. Move to 1: 1 is now a leaf. New Structure: 3 -> 2 -> 1.

Common mistakes candidates make

• Creating Cycles: Forgetting to remove the old child pointer from the parent before making the parent a child of its former child.
• Losing Subtrees: Failing to preserve the subtrees of nodes that are not on the path between the old and new roots.
• Binary Constraint Violation: Not checking if a node already has two children before adding the old parent as a new child.

Interview preparation tip

Rerooting is essentially a "Graph" operation. Sometimes it's easier to think of the tree as an undirected graph, find the path, and then reconstruct the tree from the new root using BFS or DFS.