Change the Root of a Binary Tree

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 theleaf up to the root​​​ excluding the root :

1. If cur has a left child, then that child becomes cur's right child.
2. 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:

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].
• -10^9 <= 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

1. Find the path from the leaf up to the root using parent pointers.
2. 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.
3. Set the parent of the new root (leaf) to null.
4. Return the new root.

Code

C++

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;
    }
};

Go

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
}

Java

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;
    }
}

Kotlin

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
    }
}

Python

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

Rust

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