LeetCode 1666 - Change the Root of a Binary Tree

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

This problem asks us to reroot a binary tree at a given leaf node. Normally, a binary tree has a single root, and every node points downward to its children. In this problem, each node also contains a parent pointer, which allows traversal upward toward the root.

We are given two inputs:

root, the current root of the binary tree
leaf, a node that is guaranteed to be a leaf somewhere in the tree

Our task is to transform the tree so that the given leaf becomes the new root.

The rerooting process follows a very specific rule. Starting from the leaf and moving upward toward the original root:

If the current node already has a left child, that left child must become the current node's right child.
The current node's parent becomes its left child.
The original connection from the parent back to the current node must be removed.

This operation is repeated for every node on the path from the leaf to the original root, excluding the original root itself.

The important detail is that we must correctly maintain both:

child pointers (left and right)
parent pointers (parent)

A solution that only updates the tree structure but forgets to update parent references will fail.

The constraints are small, at most 100 nodes, which means efficiency is not extremely critical. However, the tree manipulation must still be logically correct because pointer updates can easily create cycles or leave dangling references.

Some important edge cases immediately stand out:

The leaf might already be directly connected to the root.
A node on the rerooting path may already have a left child, which must be shifted to the right.
The current node could be either the left child or right child of its parent, so we must disconnect the correct pointer.
Incorrect pointer updates could create cycles in the tree.
The original root may still retain references to old children unless explicitly cleaned up.

Because every node value is unique and the leaf is guaranteed to exist in the tree, we do not need to worry about ambiguity or invalid inputs.

Approaches

Brute Force Approach

A brute force strategy would attempt to completely rebuild the tree from scratch after identifying the path from the leaf to the root.

One possible implementation would:

Perform a DFS or BFS to record the entire tree structure.
Extract the path from the leaf to the root.
Create a brand new tree where edges along that path are reversed.
Reattach every unaffected subtree manually.

This works because rerooting fundamentally means reversing parent-child relationships along a single path. By reconstructing the entire structure explicitly, we can guarantee correctness.

However, this approach is unnecessarily complicated. Rebuilding the tree requires extensive bookkeeping and introduces many opportunities for mistakes when reconnecting subtrees and parent pointers.

Even though the constraints are small, rebuilding the whole structure is inefficient compared to directly modifying pointers in place.

Optimal Approach

The key insight is that only the nodes on the path from the leaf to the root change direction.

Every other subtree remains attached exactly where it already was.

Therefore, instead of reconstructing the tree, we can walk upward from the leaf and locally reverse the parent-child relationships one step at a time.

At each node:

preserve any existing left child by moving it to the right
make the parent become the new left child
disconnect the old parent reference
continue upward

This resembles reversing a linked list, except each node can also contain another subtree that must be preserved correctly.

Because we only traverse the root-to-leaf path once, the algorithm is both simple and efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Rebuilds the tree structure from scratch
Optimal	O(n)	O(1)	Reverses pointers in place along the leaf-to-root path

Algorithm Walkthrough

Start from the given leaf node.

This node will eventually become the new root. We will walk upward toward the original root using parent pointers. 2. Store the current node's parent before modifying pointers.

Once we begin changing child relationships, the original structure will be altered. We therefore save the parent reference first so we can continue traversing upward safely. 3. If the current node has a left child, move it to the right child position.

The problem statement explicitly requires this transformation. We do this before assigning a new left child because the left pointer will soon be overwritten with the parent node. 4. Make the original parent become the current node's left child.

This reverses the direction of the edge between the current node and its parent. 5. Disconnect the original parent's reference to the current node.

The parent may reference the current node through either its left or right pointer. We check both possibilities and set the correct one to None.

This step is critical because failing to disconnect the old edge creates cycles. 6. Update parent pointers carefully.

The current node's parent becomes the previous node processed in the rerooting chain.
The original parent's parent will later be updated when processing continues upward.

Move upward to the original parent and repeat.

Continue until reaching the original root. 8. Finalize the new root.

Once traversal finishes, the original leaf becomes the new root, so its parent pointer must be None.

Why it works

The algorithm works because each iteration reverses exactly one edge along the unique path from the leaf to the root.

At every step:

the old parent-child relationship is removed
the reverse relationship is created
unaffected subtrees remain attached correctly

Since every edge on the path is reversed exactly once, and no cycles are left behind, the final structure is a valid binary tree rooted at the original leaf.

Python Solution

"""
# Definition for a Node.
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
"""

from typing import Optional

class Solution:
    def flipBinaryTree(self, root: 'Node', leaf: 'Node') -> 'Node':
        current = leaf
        previous = None

        while current != root:
            parent = current.parent

            # Preserve existing left child by moving it to the right
            if current.left:
                current.right = current.left

            # Reverse the edge
            current.left = parent

            # Disconnect parent from current
            if parent.left == current:
                parent.left = None
            elif parent.right == current:
                parent.right = None

            # Update parent pointer
            current.parent = previous

            # Move upward
            previous = current
            current = parent

        # Final root processing
        current.parent = previous

        # Disconnect any leftover child reference
        if current.left == previous:
            current.left = None
        elif current.right == previous:
            current.right = None

        return leaf

The implementation directly follows the pointer reversal strategy described earlier.

The variable current tracks the node currently being processed while walking upward from the leaf. The variable previous represents the node that has already been rerooted beneath the current node.

Before changing any structure, the algorithm stores parent = current.parent. This is necessary because the parent-child relationship will soon be reversed.

If the current node already has a left child, it gets shifted to the right side. This preserves the subtree before overwriting the left pointer.

The edge reversal happens with:

current.left = parent

At this point, the parent still points back to the current node, so the old reference must be removed. The code checks whether the current node was attached as a left or right child and disconnects the correct pointer.

Finally, parent pointers are updated so the rerooted structure remains consistent.

The loop stops once the original root is reached. After exiting the loop, the original root still needs cleanup because it may still reference the rerooted chain.

The function ultimately returns leaf, which is now the new root.

Go Solution

/**
 * Definition for a Node.
 * type Node struct {
 *     Val    int
 *     Left   *Node
 *     Right  *Node
 *     Parent *Node
 * }
 */

func flipBinaryTree(root *Node, leaf *Node) *Node {
	current := leaf
	var previous *Node = nil

	for current != root {
		parent := current.Parent

		// Preserve existing left child
		if current.Left != nil {
			current.Right = current.Left
		}

		// Reverse the edge
		current.Left = parent

		// Disconnect parent from current
		if parent.Left == current {
			parent.Left = nil
		} else if parent.Right == current {
			parent.Right = nil
		}

		// Update parent pointer
		current.Parent = previous

		previous = current
		current = parent
	}

	// Final cleanup for original root
	current.Parent = previous

	if current.Left == previous {
		current.Left = nil
	} else if current.Right == previous {
		current.Right = nil
	}

	return leaf
}

The Go implementation is structurally almost identical to the Python version.

The primary difference is explicit pointer handling using nil instead of None. Go also requires explicit variable declarations and type annotations.

Because Go uses pointers directly, tree manipulation remains efficient and in place without additional allocations.

Worked Examples

Example 1

Initial tree:

Leaf = 7

Path from leaf to root:

7 -> 2 -> 5 -> 3

Step-by-step transformation

Step	Current	Parent	Action
1	7	2	Set 7.left = 2
2	2	5	Move 2.left (7) to 2.right, set 2.left = 5
3	5	3	Move 5.left (6) to 5.right, set 5.left = 3
4	3	None	Cleanup final root

Final tree

Serialized output:

[7,2,null,5,4,3,6,null,null,null,1,null,null,0,8]

Example 2

Initial tree:

Leaf = 0

Path:

0 -> 1 -> 3

Step-by-step transformation

Step	Current	Parent	Action
1	0	1	Set 0.left = 1
2	1	3	Move 1.left (0) to 1.right, set 1.left = 3
3	3	None	Cleanup final root

Final tree

Serialized output:

[0,1,null,3,8,5,null,null,null,6,2,null,null,7,4]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	In the worst case, the leaf-to-root path contains all nodes
Space	O(1)	The algorithm modifies pointers in place without extra data structures

The algorithm only traverses the path from the selected leaf to the root once. Every pointer update is constant time, so the total complexity is proportional to the number of nodes on that path.

No recursion, stacks, or auxiliary collections are used, so the extra space usage remains constant.

Test Cases

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None

def connect(parent, left=None, right=None):
    parent.left = left
    parent.right = right

    if left:
        left.parent = parent

    if right:
        right.parent = parent

def serialize(root):
    from collections import deque

    result = []
    queue = deque([root])

    while queue:
        node = queue.popleft()

        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)

    while result and result[-1] is None:
        result.pop()

    return result

sol = Solution()

# Example 1
n3 = Node(3)
n5 = Node(5)
n1 = Node(1)
n6 = Node(6)
n2 = Node(2)
n0 = Node(0)
n8 = Node(8)
n7 = Node(7)
n4 = Node(4)

connect(n3, n5, n1)
connect(n5, n6, n2)
connect(n1, n0, n8)
connect(n2, n7, n4)

new_root = sol.flipBinaryTree(n3, n7)

assert serialize(new_root) == [
    7, 2, None, 5, 4, 3, 6,
    None, None, None, 1, None, None, 0, 8
], "Example 1 rerooting"

# Example 2
n3 = Node(3)
n5 = Node(5)
n1 = Node(1)
n6 = Node(6)
n2 = Node(2)
n0 = Node(0)
n8 = Node(8)
n7 = Node(7)
n4 = Node(4)

connect(n3, n5, n1)
connect(n5, n6, n2)
connect(n1, n0, n8)
connect(n2, n7, n4)

new_root = sol.flipBinaryTree(n3, n0)

assert serialize(new_root) == [
    0, 1, None, 3, 8, 5,
    None, None, None, 6, 2, None, None, 7, 4
], "Example 2 rerooting"

# Smallest valid tree
a = Node(1)
b = Node(2)

connect(a, b, None)

new_root = sol.flipBinaryTree(a, b)

assert new_root.val == 2, "Two-node tree root"
assert new_root.left.val == 1, "Parent becomes left child"

# Leaf directly attached to root
a = Node(10)
b = Node(20)
c = Node(30)

connect(a, b, c)

new_root = sol.flipBinaryTree(a, c)

assert new_root.val == 30, "Direct child reroot"
assert new_root.left.val == 10, "Root becomes child"

# Verify parent pointers
a = Node(1)
b = Node(2)
c = Node(3)

connect(a, b, None)
connect(b, c, None)

new_root = sol.flipBinaryTree(a, c)

assert new_root.parent is None, "New root parent should be None"
assert new_root.left.parent == new_root, "Parent pointer correctness"

Test	Why
Example 1	Validates rerooting through multiple levels
Example 2	Validates rerooting through the opposite subtree
Two-node tree	Tests minimum valid input size
Direct child reroot	Ensures simple one-edge reversal works
Parent pointer validation	Confirms parent references are updated correctly

Edge Cases

One important edge case occurs when the tree contains only two nodes. In this scenario, the leaf is directly connected to the root, and rerooting requires only a single edge reversal. A buggy implementation might accidentally leave the original root pointing back to the leaf, creating a cycle. The solution handles this by explicitly disconnecting the parent reference during every iteration.

Another subtle case happens when a node on the rerooting path already has a left child. According to the problem rules, that subtree must not be discarded. Instead, it becomes the node's right child before the parent is attached as the new left child. Forgetting this step would lose part of the tree structure. The implementation preserves the subtree by moving current.left into current.right before overwriting the left pointer.

A third critical edge case involves parent pointers. Many tree problems only require updating child references, but this problem explicitly validates parent links as well. If the new root still has a non-null parent, or if intermediate nodes reference outdated parents, the solution will fail. The implementation carefully updates every node's parent field during rerooting and explicitly ensures the final root has parent = None.