1666. Change the Root of a Binary Tree

Problem Description

In this problem, we are given the root of a binary tree and a leaf node. Our task is to reroot the binary tree so that this leaf node becomes the new root of the tree. The transformation needs to follow certain steps, and they must be applied starting from the leaf node in question towards the original root (but not including it). The steps are:

If the current node (cur) has a left child, that child should now become the right child of cur.
The previous parent of cur now becomes the left child of cur. It's important to ensure here that the old connection between cur and its parent is severed, resulting in the parent having at most one child.

The final requirement is to return the new root of the rerooted tree, which is the leaf node we started with. Throughout this process, we must make sure that the parent pointers in the tree's nodes are updated correctly, or the solution will be incorrect.

Flowchart Walkthrough

To address LeetCode 1666. Change the Root of a Binary Tree, we will use the algorithm flowchart to select the most appropriate algorithm. Let's walk through the decision-making process using the flowchart:

Is it a graph?
- Yes: A binary tree is a type of graph.
Is it a tree?
- Yes: Specifically, the problem is based on a binary tree structure.
DFS
- The flowchart directs us to use Depth-First Search (DFS) when we identify the structure as a tree.

Conclusion: Based on this analysis and the structure of the problem being centered around a tree, the flowchart suggests using DFS to solve this problem of changing the root of a binary tree. This algorithm will effectively traverse and manipulate nodes to rearrange the tree with the new root.

Intuition

The solution follows a simple yet effective approach. Beginning with the leaf node that's supposed to become the new root, we move upwards towards the original root, performing the required transformation at each step:

We flip the current node's left and right children (if the left child exists).
We then make the current node's parent the new left child of the current node, ensuring that we cut off the parent's link to the current node.
We proceed to update the current node to be the former parent, and repeat the process until we reach the original root.

With each step, the parent pointer of the nodes is updated to reflect the rerooting process. This ensures that once we reach the original root, our leaf node has successfully become the new root with the entire binary tree rerooted accordingly. Notably, the final step is to sever the parent connection of the leaf node, as it is now the root of the tree and should not have a parent.

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

Solution Approach

To implement the solution, we follow a specific set of steps that involve traversing from the leaf node up to the original root and rearranging the pointers in such a way that the leaf node becomes the new root.

Here's a walkthrough of the implementation using the solution code given:

We start by initializing cur as the leaf node, which is our target for the new root. We will move cur up the tree, so we also initialize p to be the parent of cur.
We then enter a loop that will continue until cur becomes equal to the original root. Inside this loop, we perform the steps needed to reroot the tree:
- We store the parent of the parent (gp) for a later step, as it will become the parent of p in the next iteration.
- If cur.left exists, we make it the right child of cur by doing cur.right = cur.left.
- We then set cur.left to p, making the original parent (p) the new left child of cur.
- After changing the child pointers, we update the parent pointer by setting p.parent to cur.
- We need to ensure that p will no longer have cur as a child, hence we check whether cur was a left or right child and then set the respective child pointer in p to None.
- We move up the tree by setting cur to p and p to gp.
After the loop, the original leaf node is now at the position of the new root, but the parent pointer for this new root is still set. We must set leaf.parent to None to finalize the rerooting process.
The last step is to return leaf, which is now the new root following the rerooting algorithm described above.

The main algorithmic concept here is the traversal and pointer manipulation in a binary tree. The traversal is not recursive but iterative, using a while loop to go node by node upwards towards the original root. The pointers manipulations involve changes to both child and parent pointers, as per the rerooting steps.

Remember that while the mechanism may appear simple, it is crucial to handle the pointers correctly to avoid any cycles or incorrect hierarchy in the transformed tree structure.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small binary tree and the steps required to reroot it using the solution described.

Original Binary Tree:

      a
     / \
    b   c
   / \
  d   e
 /
f

Goal: Reroot the tree so the leaf node f becomes the new root.

Starting Point: Node f.

Using our approach:

Initialize cur as node f. Since f has no left child, we do not modify its right child.
Set p as the parent of f, which is node d.
In the loop:
- Set gp (grandparent) as the parent of d, which is node b.
- Since cur.left does not exist, we move to the next step.
- Make d the left child of f by setting cur.left to p, so now f points to d on the left.
- Set the parent pointer of d (p.parent) to f.
- Determine if f was a left or right child of d. In this case, f is the left child, so set d.left to None.
- Move up the tree: cur now becomes d, and p becomes b.
Next loop iteration:
- Set gp as the parent of b, which is node a.
- Now cur.left exists (e), so set cur.right to cur.left (make d.right point to e).
- Make b the left child of d by setting cur.left to p.
- The parent pointer of b (p.parent) is set to d.
- Determine if d was a left or right child of b. d is the left child, so set b.left to None.
- Move up: cur now is b, and p is a.
Final loop iteration:
- gp would be the parent of a, which does not exist since a is the original root.
- cur.left does not exist (tree doesn’t have b.left anymore), so no changes to cur.right.
- Make a the left child of b by setting cur.left to p.
- The parent pointer of a (p.parent) is now set to b.
- Determine if b was a left or right child of a. b is the left child, so set a.left to None.
- Since a has no parent (gp), exit the loop.

Final Step: Set the parent of the new root (f) to None as it should not have a parent.

Resulting Rerooted Binary Tree:

Now, f is the new root, and the tree is correctly rerooted, preserving the left and right subtrees’ hierarchy where applicable.

Solution Implementation

1class Solution:
2    def flipBinaryTree(self, root: 'Node', leaf: 'Node') -> 'Node':
3        # Initialize current node as the leaf node.
4        current_node = leaf
5        parent_node = current_node.parent
6      
7        # Traverse up the tree until we reach the root.
8        while current_node != root:
9            # Keep reference to the grandparent node.
10            grandparent_node = parent_node.parent
11          
12            # If current node has a left child, move it to the right side.
13            if current_node.left:
14                current_node.right = current_node.left
15              
16            # Make the parent node a left child of the current node.
17            current_node.left = parent_node
18            parent_node.parent = current_node
19          
20            # Disconnect the current node from the old place in the tree.
21            if parent_node.left == current_node:
22                parent_node.left = None
23            elif parent_node.right == current_node:
24                parent_node.right = None
25          
26            # Move one level up the tree
27            current_node = parent_node
28            parent_node = grandparent_node
29      
30        # Once the root is reached, we disconnect the leaf from its parent.
31        leaf.parent = None
32      
33        # The original leaf node is now the new root of the flipped tree.
34        return leaf
35

1class Solution {
2    public Node flipBinaryTree(Node root, Node leaf) {
3        // Initialize current node as the leaf node to be flipped up to the new root position.
4        Node currentNode = leaf;
5        // Initialize parent node as the parent of the current node.
6        Node parentNode = currentNode.parent;
7
8        // Iterate until the current node is the original root.
9        while (currentNode != root) {
10            // Store the grandparent node (parent of the parent node) for later use.
11            Node grandParentNode = parentNode.parent;
12
13            // If the current node has a left child, move it to the right child position.
14            if (currentNode.left != null) {
15                currentNode.right = currentNode.left;
16            }
17          
18            // Flip the link direction between current node and parent node.
19            currentNode.left = parentNode;
20
21            // Update the parent's parent to point back to the current node.
22            parentNode.parent = currentNode;
23
24            // Disconnect the current node from its original position in its parent node.
25            if (parentNode.left == currentNode) {
26                parentNode.left = null;
27            } else if (parentNode.right == currentNode) {
28                // It must be from the right child position.
29                parentNode.right = null;
30            }
31
32            // Move up the tree: Set current node to parent, and parent node to grandparent.
33            currentNode = parentNode;
34            parentNode = grandParentNode;
35        }
36
37        // After flipping the tree, the original leaf node has no parent.
38        leaf.parent = null;
39
40        // Return the new root of the flipped binary tree (which was the original leaf node).
41        return leaf;
42    }
43}
44

1// Definition for a binary tree node with an additional parent pointer
2class Node {
3public:
4    int val;        // The value of the node
5    Node* left;     // Pointer to the left child
6    Node* right;    // Pointer to the right child
7    Node* parent;   // Pointer to the parent node
8};
9
10class Solution {
11public:
12    Node* flipBinaryTree(Node* root, Node* leaf) {
13        Node* current = leaf;           // Initialize current node to leaf
14        Node* parent = current->parent; // Parent node of the current node
15
16        // Continue flipping the tree until we reach the root
17        while (current != root) {
18            Node* grandParent = parent->parent; // Grandparent node of the current node
19
20            // If there is a left child, make it the right child for flip operation
21            if (current->left) {
22                current->right = current->left;
23            }
24
25            // Connect the parent to the current node's left for flip operation
26            current->left = parent;
27
28            // Update the parent's new parent to be the current node
29            parent->parent = current;
30
31            // Disconnect the old links from the parent to the current node
32            if (parent->left == current) {
33                parent->left = nullptr; // Previous left child
34            } else if (parent->right == current) {
35                parent->right = nullptr; // Previous right child
36            }
37
38            // Move up the tree
39            current = parent;
40            parent = grandParent;
41        }
42
43        // Finally, ensure the new root (originally the leaf) has no parent
44        leaf->parent = nullptr;
45
46        // Return new root of the flipped tree
47        return leaf;
48    }
49};
50

1// Node class definition for a binary tree with a parent reference.
2interface Node {
3    val: number;
4    left: Node | null;
5    right: Node | null;
6    parent: Node | null;
7}
8
9/**
10 * Flips the binary tree so that the path from the specified leaf node to the root becomes the rightmost path in the resulting tree, and all nodes along the path have their left and right children swapped, preserving subtree structures.
11 * 
12 * @param {Node} root - The root node of the binary tree.
13 * @param {Node} leaf - The leaf node that will become the new root after flipping.
14 * @return {Node} - The new root of the flipped binary tree (which is the leaf node).
15 */
16var flipBinaryTree = function(root: Node, leaf: Node): Node {
17    let currentNode: Node | null = leaf; // Start with the leaf node.
18    let parent: Node | null = currentNode.parent; // Get the parent of the current node.
19
20    // Iterate until we reach the root of the initial tree.
21    while (currentNode !== root) {
22        const grandParent: Node | null = parent ? parent.parent : null; // Save the grandparent node.
23
24        if (currentNode.left !== null) {
25            currentNode.right = currentNode.left; // Move the left subtree to the right.
26        }
27        currentNode.left = parent; // The parent becomes the left child of the current node.
28
29        if (parent) {
30            parent.parent = currentNode; // Update the parent's parent to the current node.
31
32            // Disconnect the current node from its former parent node.
33            if (parent.left === currentNode) {
34                parent.left = null;
35            } else if (parent.right === currentNode) {
36                parent.right = null;
37            }
38        }
39
40        // Move up the tree.
41        currentNode = parent;
42        parent = grandParent;
43    }
44
45    if (leaf) {
46        leaf.parent = null; // Detach the new root from any parents.
47    }
48  
49    // The initial leaf node is now the root of the flipped tree.
50    return leaf;
51};
52

Time and Space Complexity

Time Complexity

The given code processes each node starting from the leaf towards the root, reversing the connections by making each node's parent its child until it reaches the root. Each node is visited exactly once during this process. Therefore, the time complexity is O(N), where N is the number of nodes from leaf to root inclusive, which in the worst case can be the height of the tree.

Space Complexity

The space complexity is O(1) since the function only uses a fixed amount of additional space for pointers cur, p, and gp regardless of the input size. The modifications are done in place, so no additional space that depends on the size of the tree is required.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: