Watch the video solution for Change the Root of a Binary Tree, a medium level problem involving Tree, Depth-First Search, Binary Tree. This walkthrough by AlitaCode has 16 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given the root of a binary tree and a leaf node, reroot the tree so that the leaf is the new root.
You can reroot the tree with the following steps for each node cur on the path starting from the leaf up to the root excluding the root:
cur has a left child, then that child becomes cur's right child.cur's original parent becomes cur's left child. Note that in this process the original parent's pointer to cur becomes null, making it have at most one child.Return the new root of the rerooted tree.
Note: Ensure that your solution sets the Node.parent pointers correctly after rerooting or you will receive "Wrong Answer".
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], leaf = 7 Output: [7,2,null,5,4,3,6,null,null,null,1,null,null,0,8]
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], leaf = 0 Output: [0,1,null,3,8,5,null,null,null,6,2,null,null,7,4]
Constraints:
[2, 100].-109 <= Node.val <= 109Node.val are unique.leaf exist in the tree.Problem Overview: You’re given a binary tree where every node has a parent pointer. A specific leaf node must become the new root. The task is to reverse the parent-child relationships along the path from that leaf to the original root while keeping the rest of the tree valid.
Approach 1: Path Collection and Rebuild (O(n) time, O(n) space)
First walk from the given leaf up to the original root using the parent pointers and store every node in a list. This gives you the exact path that needs to be reversed. Iterate through this path and reconnect pointers so each node becomes the parent of the previous one. While doing this, move existing left/right children if needed to maintain the binary tree structure. The extra array simplifies reasoning but adds O(n) space for storing the path.
This approach is useful if you want clearer logic during implementation or debugging. Explicitly storing the path makes pointer rewiring easier to follow and avoids accidental cycles.
Approach 2: In-Place Pointer Reversal (O(n) time, O(1) space)
Traverse upward from the leaf using parent pointers and reverse edges on the fly. At each step, detach the current node from its parent and make the parent a child of the current node. If the current node already has a left child (which may happen during the reversal), move it to the right before attaching the parent as the new left child. Continue until reaching the original root.
This works like reversing a linked list, but with additional handling for the binary tree’s left and right children. Each node on the path is processed once, so the runtime is O(n) in the worst case (height of the tree), and no auxiliary structures are required.
The logic relies on understanding parent relationships in a tree and performing careful pointer updates while walking upward. A recursive or iterative traversal resembles patterns from depth-first search problems involving structural modifications of a binary tree.
Recommended for interviews: The in-place pointer reversal approach. It demonstrates strong understanding of tree pointer manipulation and achieves O(n) time with O(1) extra space. Showing the path-based version first can help communicate the idea, but the optimal in-place reversal is what interviewers typically expect.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Path Collection and Rebuild | O(n) | O(n) | When you want simpler reasoning by storing the entire leaf-to-root path before rewiring pointers |
| In-Place Pointer Reversal | O(n) | O(1) | Optimal interview solution when modifying pointers directly along the path to the root |