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 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”.
Examples#
Example 1:
1
2
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:
1
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 <= 10^9
All Node.val
are unique .
leaf
exist in the tree.
Solution#
Method 1 – Path Reversal with Parent Pointers#
Intuition:
To reroot the tree at the given leaf, we need to reverse the parent-child relationships along the path from the leaf to the root. At each step, we update the pointers as described, ensuring the parent pointers are also set correctly.
Approach:
Find the path from the leaf up to the root using parent pointers.
For each node on the path (from leaf up, excluding the root):
If the node has a left child, make it the right child.
The original parent becomes the left child.
Set the parent’s pointer to this node to null.
Update parent pointers accordingly.
Set the parent of the new root (leaf) to null.
Return the new root.
Code#
Cpp
Go
Java
Kotlin
Python
Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public :
Node* flipBinaryTree(Node* root, Node* leaf) {
Node* prev = nullptr ;
Node* curr = leaf;
Node* next = nullptr ;
while (curr != root) {
Node* parent = curr-> parent;
if (curr-> left) {
curr-> right = curr-> left;
}
if (parent-> left == curr) parent-> left = nullptr ;
if (parent-> right == curr) parent-> right = nullptr ;
curr-> left = parent;
curr-> parent = prev;
prev = curr;
curr = parent;
}
curr-> parent = prev;
return leaf;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
type Node struct {
Val int
Left * Node
Right * Node
Parent * Node
}
func flipBinaryTree (root , leaf * Node ) * Node {
var prev * Node
curr := leaf
for curr != root {
parent := curr .Parent
if curr .Left != nil {
curr .Right = curr .Left
}
if parent .Left == curr {
parent .Left = nil
}
if parent .Right == curr {
parent .Right = nil
}
curr .Left = parent
curr .Parent = prev
prev = curr
curr = parent
}
curr .Parent = prev
return leaf
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public Node flipBinaryTree (Node root, Node leaf) {
Node prev = null , curr = leaf, next;
while (curr != root) {
Node parent = curr.parent ;
if (curr.left != null ) curr.right = curr.left ;
if (parent.left == curr) parent.left = null ;
if (parent.right == curr) parent.right = null ;
curr.left = parent;
curr.parent = prev;
prev = curr;
curr = parent;
}
curr.parent = prev;
return leaf;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
fun flipBinaryTree (root: Node, leaf: Node): Node {
var prev: Node? = null
var curr: Node? = leaf
while (curr != root) {
val parent = curr!! .parent
if (curr.left != null ) curr.right = curr.left
if (parent.left == curr) parent.left = null
if (parent.right == curr) parent.right = null
curr.left = parent
curr.parent = prev
prev = curr
curr = parent
}
curr!! .parent = prev
return leaf
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution :
def flipBinaryTree (self, root: 'Node' , leaf: 'Node' ) -> 'Node' :
prev = None
curr = leaf
while curr != root:
parent = curr. parent
if curr. left:
curr. right = curr. left
if parent. left == curr:
parent. left = None
if parent. right == curr:
parent. right = None
curr. left = parent
curr. parent = prev
prev = curr
curr = parent
curr. parent = prev
return leaf
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
impl Solution {
pub fn flip_binary_tree (root: & mut Node, leaf: & mut Node) -> & mut Node {
let mut prev: Option<* mut Node> = None;
let mut curr: * mut Node = leaf;
unsafe {
while curr != root {
let parent = (* curr).parent;
if ! (* curr).left.is_null() {
(* curr).right = (* curr).left;
}
if (* parent).left == curr {
(* parent).left = std::ptr::null_mut();
}
if (* parent).right == curr {
(* parent).right = std::ptr::null_mut();
}
(* curr).left = parent;
(* curr).parent = prev.unwrap_or(std::ptr::null_mut());
prev = Some(curr);
curr = parent;
}
(* curr).parent = prev.unwrap_or(std::ptr::null_mut());
}
leaf
}
}
Complexity#
⏰ Time complexity: O(h)
, where h
is the height of the tree.
🧺 Space complexity: O(h)
for the path