Problem Description

You are given a binary tree where each node has pointers to its left child, right child, and parent. The task is to restructure the tree so that a given leaf node becomes the new root of the tree.

The rerooting process works by traversing from the leaf node up to the original root, and for each node along this path (except the root itself), you perform these transformations:

1. If the current node has a left child, move that left child to become the right child
2. Make the current node's parent become its new left child
3. Remove the parent's original pointer to the current node (set it to null)

This essentially "flips" the parent-child relationships along the path from the leaf to the root. After this process:

• The original leaf becomes the new root (with no parent)
• The original root becomes a leaf node
• All parent-child relationships along the path are reversed
• Nodes not on the path remain in their relative positions

For example, if you have a path: root → A → B → leaf, after rerooting it becomes: leaf → B → A → root, where each arrow now represents the reversed parent-child relationship.

The solution traverses from the leaf upward to the root, at each step:

• Saving the grandparent reference before modifying relationships
• Moving any left child to the right
• Setting the parent as the new left child
• Updating parent pointers accordingly
• Clearing the parent's original pointer to the current node

The process continues until reaching the original root, and finally returns the leaf as the new root with its parent pointer set to None.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph where each node has at most two children and there are no cycles. The problem involves nodes with parent-child relationships.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure. We have nodes connected in a hierarchical manner with a root, and each node (except the root) has exactly one parent.

DFS

• Yes: The flowchart leads us to DFS for tree problems.

Conclusion: The flowchart suggests using a Depth-First Search (DFS) approach for this binary tree problem.

This aligns perfectly with the solution approach, which uses a DFS-like traversal pattern. The algorithm traverses from the leaf node up to the root (following parent pointers), which is essentially a depth-first traversal in reverse. At each step, it modifies the tree structure by reversing parent-child relationships. The traversal visits each node on the path exactly once, manipulating pointers to reroot the tree, which is a classic application of DFS in tree manipulation problems.

Intuition

To understand how to reroot a tree, imagine holding a tree by its root and letting gravity pull all branches downward. Now, if you grab any leaf and lift it up to become the new root, what happens? The entire path from that leaf to the old root gets "flipped" - every parent-child relationship along this path reverses.

The key insight is that we only need to modify nodes along the path from the leaf to the root. All other nodes maintain their relative positions because they're not directly affected by this "lifting" operation.

Think of it like a chain of nodes connected from leaf to root. When we make the leaf the new root, we're essentially reversing this chain:

• The leaf's parent becomes the leaf's child
• The parent's parent becomes the parent's child
• This continues all the way up to the original root

For each node we visit while traversing upward, we need to:

1. Preserve any existing left child by moving it to the right (since we'll need the left spot for the parent)
2. Make the current node's parent become its left child (reversing the relationship)
3. Clear the parent's original pointer to avoid cycles

The traversal naturally follows a DFS pattern - we're exploring a single path from leaf to root, modifying relationships as we go. We need to carefully track three nodes at each step: the current node, its parent, and its grandparent. The grandparent reference is crucial because once we modify the parent-child relationship, we'd lose the ability to continue traversing upward.

This approach works because binary trees have a unique path between any two nodes. By following parent pointers from leaf to root and reversing each connection, we effectively "rotate" the tree to make the leaf the new root while preserving all other structural relationships.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

The implementation follows a straightforward iterative approach to traverse from the leaf to the root and reverse the parent-child relationships along the path.

We start by initializing two pointers:

• cur pointing to the leaf node (which will become our new root)
• p pointing to the leaf's parent

The main algorithm uses a while loop that continues until cur reaches the original root. In each iteration, we perform the following steps:

1. Save the grandparent reference: Before modifying any relationships, we store gp = p.parent. This is crucial because once we change the parent-child relationship, we'd lose access to continue traversing upward.

2. Handle existing left child: If the current node has a left child, we move it to the right position with cur.right = cur.left. This frees up the left position for the parent node.

3. Reverse the parent-child relationship:

   • Set cur.left = p to make the parent become the left child
   • Update p.parent = cur to establish the new parent pointer

4. Clear the old connection: We need to remove the parent's original pointer to the current node to avoid cycles:

   • If p.left == cur, set p.left = None
   • If p.right == cur, set p.right = None

5. Move up the tree: Update pointers for the next iteration:

   • cur = p (move current to the parent)
   • p = gp (move parent to the grandparent)

After the loop completes, the original leaf has become the new root. We finalize by setting leaf.parent = None since the root shouldn't have a parent, and return leaf as the new root.

The algorithm visits each node on the path from leaf to root exactly once, making the time complexity O(h) where h is the height of the tree. The space complexity is O(1) as we only use a constant amount of extra space for the pointers.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Consider this binary tree where we want to make node 7 (a leaf) the new root:

Initial tree:
       1 (root)
      / \
     2   3
    /
   4
  / \
 5   6
    /
   7 (leaf to become root)

We'll trace through each iteration as we traverse from leaf 7 up to root 1:

Iteration 1: cur = 7, p = 6

• Save grandparent: gp = 4
• Node 7 has no left child, so nothing to move right
• Make parent 6 the left child: 7.left = 6
• Update parent pointer: 6.parent = 7
• Clear old connection: 6.left = None (since 6's left was 7)
• Move up: cur = 6, p = 4

Tree after iteration 1:

7 → 6   (7 is now parent of 6)

Iteration 2: cur = 6, p = 4

• Save grandparent: gp = 2
• Node 6 has no left child (we just cleared it), nothing to move
• Make parent 4 the left child: 6.left = 4
• Update parent pointer: 4.parent = 6
• Clear old connection: 4.right = None (since 4's right was 6)
• Move up: cur = 4, p = 2

Tree structure building:

7 → 6 → 4   (with 4 still having left child 5)

Iteration 3: cur = 4, p = 2

• Save grandparent: gp = 1
• Node 4 has left child 5, move it right: 4.right = 5
• Make parent 2 the left child: 4.left = 2
• Update parent pointer: 2.parent = 4
• Clear old connection: 2.left = None (since 2's left was 4)
• Move up: cur = 2, p = 1

Iteration 4: cur = 2, p = 1

• Save grandparent: gp = None (1 is the root)
• Node 2 has no left child, nothing to move
• Make parent 1 the left child: 2.left = 1
• Update parent pointer: 1.parent = 2
• Clear old connection: 1.left = None (since 1's left was 2)
• Move up: cur = 1, p = None

Loop ends (p is None, cur is at original root)

Finally, set 7.parent = None to make it the proper root.

Final tree structure:

       7 (new root)
      /
     6
    /
   4
  / \
 2   5
/
1
 \
  3

The path from 7 to 1 has been completely reversed, while nodes not on this path (like 3 and 5) maintain their relative positions. Node 7 is now the root, and node 1 has become a leaf.

Solution Implementation

Time and Space Complexity

Time Complexity: O(h) where h is the height of the tree (or more precisely, the distance from the leaf node to the root node).

The algorithm traverses from the given leaf node up to the root node, visiting each node along this path exactly once. In each iteration of the while loop, we perform a constant number of operations:

• Pointer reassignments (cur.left = p, p.parent = cur, etc.)
• Conditional checks (if cur.left, if p.left == cur, etc.)

Since we visit at most h nodes (the path from leaf to root) and perform O(1) operations at each node, the total time complexity is O(h). In the worst case where the tree is skewed, h could be O(n) where n is the total number of nodes in the tree.

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space:

• Three pointer variables: cur, p, and gp
• No recursive calls (iterative approach)
• No additional data structures

The modifications are done in-place by rearranging the existing pointers in the tree structure. Therefore, the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle the Left Child Before Reassignment

One of the most common mistakes is directly assigning the parent to current_node.left without first handling any existing left child. This would cause the original left subtree to be lost.

Incorrect approach:

# This loses the original left child!
current_node.left = parent_node  # Original left child is gone

Correct approach:

# First move the left child to the right (if it exists)
if current_node.left:
    current_node.right = current_node.left
# Then assign the parent as the new left child
current_node.left = parent_node

2. Not Saving the Grandparent Reference Before Modifications

Another critical mistake is trying to access parent_node.parent after modifying the parent-child relationships. Once you change parent_node.parent = current_node, you lose access to the original grandparent.

Incorrect approach:

while current_node != root:
    # Modify relationships first
    current_node.left = parent_node
    parent_node.parent = current_node

    # This now points to current_node, not the original grandparent!
    grandparent = parent_node.parent  # Wrong!

Correct approach:

while current_node != root:
    # Save grandparent BEFORE any modifications
    grandparent_node = parent_node.parent

    # Now safe to modify relationships
    current_node.left = parent_node
    parent_node.parent = current_node

3. Creating Cycles by Not Clearing Old Parent-to-Child Pointers

Failing to remove the parent's original pointer to the current node creates a cycle in the tree structure, where nodes point to each other as both parent and child.

Incorrect approach:

# After making parent the left child of current
current_node.left = parent_node
parent_node.parent = current_node
# But parent_node still has a child pointer to current_node!
# This creates a cycle: current → parent → current

Correct approach:

# Clear the old connection from parent to current
if parent_node.left == current_node:
    parent_node.left = None
elif parent_node.right == current_node:
    parent_node.right = None

4. Incorrect Loop Termination Condition

Using parent_node != None as the loop condition would cause the algorithm to miss processing the root node's transformation, leaving the tree structure incomplete.

Incorrect approach:

# This stops too early, before processing the root
while parent_node:  # Wrong condition
    # Process nodes...

Correct approach:

# Continue until current_node reaches the original root
while current_node != root:
    # Process nodes...

5. Forgetting to Clear the New Root's Parent Pointer

After the transformation, the leaf becomes the new root and should have no parent. Forgetting to set leaf.parent = None leaves an invalid parent pointer.

Solution: Always remember to finalize with:

leaf.parent = None
return leaf