We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Change the Root of a Binary Tree

Number: 1810

Difficulty: Medium

Paid? Yes

Companies: Microsoft, Google

Problem Description

Given the root of a binary tree and a target leaf node, change the root of the tree so that the given leaf becomes the new root. The rerooting must be done according to the following rules for every node cur on the path from the leaf (inclusive) up to but not including the original root:

  1. If cur has a left child, then that left child becomes cur’s right child.
  2. cur’s original parent becomes cur’s left child. All corresponding parent pointers must be updated correctly.

Key Insights

  • The transformation only affects the chain of nodes on the path from the given leaf up to the original root.
  • At each step, we “reverse” the pointer between the current node and its parent.
  • If the current node originally had a left child (which might not be part of the chain), it must be moved to become its right child.
  • It is important to detach the link from the parent to the current node so that, after the rerooting, each node (aside from the new root) has only one parent.
  • Care must be taken to update all parent pointers so that the final tree is consistent.

Space and Time Complexity

Time Complexity: O(H) where H is the height of the tree. In the worst-case (skewed tree), H = O(N). Space Complexity: O(1) extra space if using an iterative approach (ignoring recursion stack) or O(H) if recursion is used.

Solution

We solve the problem by “reversing” the pointers along the chain from the given leaf to the original root. First, we keep a reference to the new root (the given leaf). Then, for the current node cur, while its parent exists, we do the following:

  1. Save the current left child (if any) so that it can be used to update the right child.
  2. If the current node has a left child, move it to be the right child.
  3. Make the original parent of cur become its left child.
  4. Detach cur from its original parent by nulling out the parent's pointer to cur.
  5. Update the parent pointer of the original parent so that it now points back to cur.
  6. Move cur up to its parent (which has now become a child of the previous cur) and continue. After the loop ends the given leaf remains our new root; just ensure its parent pointer is set to null.

This method uses an iterative approach with constant extra space. The crux is careful pointer manipulation based on the instructions, essentially “reversing” the singly–linked chain stored in the parent pointers while preserving the non-chain left child (by reassigning it to the right child).

Code Solutions

# Definition of a binary tree node.
class Node:
    def __init__(self, val, left=None, right=None, parent=None):
        self.val = val
        self.left = left
        self.right = right
        self.parent = parent

def changeRoot(leaf):
    # Store the new root (given leaf node)
    new_root = leaf
    
    # Iteratively reverse the pointers on the chain from leaf to original root.
    cur = leaf
    while cur.parent is not None:
        parent = cur.parent  # get original parent
        
        # Step 1: If cur has a left child, move it into the right pointer.
        original_left = cur.left
        if original_left is not None:
            cur.right = original_left
            # update the moved child’s parent pointer to point to cur
            original_left.parent = cur
            
        # Step 2: Make the original parent become the left child of cur.
        cur.left = parent
        
        # Detach cur from its parent.
        if parent.left == cur:
            parent.left = None
        elif parent.right == cur:
            parent.right = None
        
        # Update parent's parent pointer so that parent's parent becomes cur.
        parent.parent = cur
        
        # Move upward in the chain.
        cur = parent
        
    # Set the new root's parent to None.
    new_root.parent = None
    return new_root

# Example usage:
# (Assuming that the tree has been built with Node objects and proper parent pointers)
# new_root = changeRoot(target_leaf)
← Back to All Questions