Skip to main content
Talentd

Change the Root of a Binary Tree - Solution & Explanation

MediumPremiumFree on FleetCodeTreeDepth-First SearchBinary Tree6 min readAsked at: Google
Practice this problem

Problem Statement

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:

  1. If cur has a left child, then that child becomes cur's right child.
  2. 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:

  • The number of nodes in the tree is in the range [2, 100].
  • -109 <= Node.val <= 109
  • All Node.val are unique.
  • leaf exist in the tree.

Approach Overview

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.

Solution

Code

PythonJavaC++JavaScriptC#

Python

Java

C++

JavaScript

C#

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Path Collection and RebuildO(n)O(n)When you want simpler reasoning by storing the entire leaf-to-root path before rewiring pointers
In-Place Pointer ReversalO(n)O(1)Optimal interview solution when modifying pointers directly along the path to the root

Video Solution

LeetCode 1666: Change the Root of a Binary Tree • AlitaCode • 18 views views

Frequently Asked Questions

Is Change the Root of a Binary Tree easy or hard?
Change the Root of a Binary Tree is rated Medium difficulty on LeetCode. The main challenge is correctly updating parent, left, and right pointers without creating cycles or losing subtrees. Once the pointer reversal pattern is understood, the implementation becomes straightforward.
Change the Root of a Binary Tree Python/Java solution
Most solutions implement an iterative traversal from the leaf to the root and update pointers during the walk. Python, Java, C++, and JavaScript implementations follow the same idea: reverse parent-child links step by step while maintaining valid left and right child references.
How to solve Change the Root of a Binary Tree in O(n)?
Start from the target leaf and move upward using the parent pointer. At each step, detach the node from its parent and make the parent a child of the current node while adjusting left and right pointers. This effectively reverses the path from the leaf to the root and produces the new root in linear time.
What is the best approach for Change the Root of a Binary Tree?
The best approach is in-place pointer reversal along the path from the given leaf to the original root. Traverse upward using parent pointers and reverse the relationships so the parent becomes a child of the current node. Each node on the path is processed once, giving O(n) time and O(1) extra space.
Is Change the Root of a Binary Tree asked at Google/Amazon/Meta?
Tree pointer manipulation and re-rooting problems appear in interviews at companies like Google, Amazon, and Meta. Variants that require modifying parent-child relationships or restructuring trees are common in senior-level coding rounds focused on data structures.
What data structure is used in Change the Root of a Binary Tree?
The problem uses a binary tree where each node contains left, right, and parent pointers. The solution relies on tree traversal and pointer manipulation, often implemented using a depth-first style upward traversal through parent links.
What is the time complexity of Change the Root of a Binary Tree?
The time complexity is O(n) in the worst case, where n is the number of nodes in the tree. Only the nodes along the path from the leaf to the root are modified, which is bounded by the tree height. Space complexity can be O(1) with an in-place approach or O(n) if the path is stored in an auxiliary list.

Ready to solve this problem?

Practice Change the Root of a Binary Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Inorder Traversal

Next

Unique Binary Search Trees II