Change the Root of a Binary Tree solution and explanation
Google
The problem
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:
- If
curhas a left child, then that child becomescur's right child. cur's original parent becomescur's left child. Note that in this process the original parent's pointer tocurbecomesnull, 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.valare unique. leafexist 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
"""
# Definition for a Node.
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.parent = None
"""
class Solution:
def flipBinaryTree(self, root: "Node", leaf: "Node") -> "Node":
cur = leaf
p = cur.parent
while cur != root:
gp = p.parent
if cur.left:
cur.right = cur.left
cur.left = p
p.parent = cur
if p.left == cur:
p.left = None
elif p.right == cur:
p.right = None
cur = p
p = gp
leaf.parent = None
return leaf/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node parent;
};
*/
class Solution {
public Node flipBinaryTree(Node root, Node leaf) {
Node cur = leaf;
Node p = cur.parent;
while (cur != root) {
Node gp = p.parent;
if (cur.left != null) {
cur.right = cur.left;
}
cur.left = p;
p.parent = cur;
if (p.left == cur) {
p.left = null;
} else if (p.right == cur) {
p.right = null;
}
cur = p;
p = gp;
}
leaf.parent = null;
return leaf;
}
}/*
// Definition for a Node->
class Node {
public:
int val;
Node* left;
Node* right;
Node* parent;
};
*/
class Solution {
public:
Node* flipBinaryTree(Node* root, Node* leaf) {
Node* cur = leaf;
Node* p = cur->parent;
while (cur != root) {
Node* gp = p->parent;
if (cur->left) {
cur->right = cur->left;
}
cur->left = p;
p->parent = cur;
if (p->left == cur) {
p->left = nullptr;
} else if (p->right == cur) {
p->right = nullptr;
}
cur = p;
p = gp;
}
leaf->parent = nullptr;
return leaf;
}
};/**
* // Definition for a Node.
* function Node(val) {
* this.val = val;
* this.left = null;
* this.right = null;
* this.parent = null;
* };
*/
/**
* @param {Node} node
* @return {Node}
*/
var flipBinaryTree = function (root, leaf) {
let cur = leaf;
let p = cur.parent;
while (cur != root) {
const gp = p.parent;
if (cur.left != null) {
cur.right = cur.left;
}
cur.left = p;
p.parent = cur;
if (p.left == cur) {
p.left = null;
} else if (p.right == cur) {
p.right = null;
}
cur = p;
p = gp;
}
leaf.parent = null;
return leaf;
};/*
// Definition for a Node.
public class Node {
public int val;
public Node left;
public Node right;
public Node parent;
}
*/
public class Solution {
public Node FlipBinaryTree(Node root, Node leaf) {
Node cur = leaf;
Node p = cur.parent;
while (cur != root) {
Node gp = p.parent;
if (cur.left != null) {
cur.right = cur.left;
}
cur.left = p;
p.parent = cur;
if (p.left == cur) {
p.left = null;
} else if (p.right == cur) {
p.right = null;
}
cur = p;
p = gp;
}
leaf.parent = null;
return leaf;
}
}Complexity analysis
| 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 |
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.