Leetcode 1666. Change the Root of a Binary Tree

Problem Explanation:

This problem asks to change the root of a given binary tree to one of the leaf nodes. A binary tree is a hierarchical data structure in which each node has at most two children, which are referred to as the left child and the right child.

We are given a binary tree and one of its leaf nodes. The task is to make this leaf node the root of the tree by flipping the tree.

Let's consider an example for a better understanding:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], leaf = 7

The actual binary tree looks like this -

1
2
3        3
4       / \
5      5   1
6     / \ / \
7    6  2 0  8
8      / \
9     7   4

If we reroot this tree so the leaf node with value '7' becomes the root, the binary tree will look as follows:

1
2
3      7
4     /
5    2
6   / \
7  5   4
8 /  
93  
10 \
11  6 

Solution Explanation:

To solve this problem, we can use the depth-first search (DFS) algorithm which is an algorithm for traversing or searching tree or graph data structures.

We start from the leaf node and traverse to its parent while updating the children of each node. If a node has a left child and it is not the new parent, we move the left child to be the right child. We continue to repeat this process until we reach the original root node of the tree.

Python Solution:

1
2python
3class Solution:
4    def flipBinaryTree(self, root, leaf):
5        def reroot(node, newParent):
6            oldParent = node.parent
7            node.parent = newParent
8
9            # Clean up the child if it's the new parent
10            if node.left == newParent:
11                node.left = None
12            if node.right == newParent:
13                node.right = None
14
15            # If it's original root, then we're done
16            if node == root:
17                return node
18
19            # Move the left child to the right if it's not the new parent
20            if node.left:
21                node.right = node.left
22            node.left = reroot(oldParent, node)
23
24            return node
25
26        return reroot(leaf, None)

Java Solution:

1
2java
3    public class Solution {
4        public Node flipBinaryTree(Node root, Node leaf) {
5            return reroot(root, leaf, null);
6        }
7
8        private Node reroot(Node root, Node node, Node newParent) {
9            Node oldParent = node.parent;
10            node.parent = newParent;
11
12            // Clean up the child if it's the new parent
13            if(node.left == newParent)
14                node.left = null;
15            if(node.right == newParent)
16                node.right = null;
17
18            // If it's original root, then we're done
19            if(node == root)
20                return node;
21
22            // Move the left child to the right if it's not the new parent
23            if(node.left != null)
24                node.right = node.left;
25            node.left = reroot(root, oldParent, node);
26
27            return node;
28        }
29    }

Javascript Solution:

1
2javascript
3class Solution {
4    flipBinaryTree(root, leaf) {
5        function reroot(node, newParent) {
6            const oldParent = node.parent;
7            node.parent = newParent;
8
9            // Clean up the child if it's the new parent
10            if (node.left === newParent) {
11                node.left = null;
12            }
13            if (node.right === newParent) {
14                node.right = null;
15            }
16
17            // If it's original root, then we're done
18            if (node === root) {
19                return node;
20            }
21
22            // Move the left child to the right if it's not the new parent
23            if (node.left) {
24                node.right = node.left;
25            }
26            node.left = reroot(oldParent, node);
27
28            return node;
29        }
30
31        return reroot(leaf, null);
32    }
33}

C++ Solution:

1
2cpp
3class Solution {
4public:
5    Node* flipBinaryTree(Node* root, Node* leaf) {
6        return reroot(root, leaf, nullptr);
7    }
8private:
9    Node* reroot(Node* root, Node* node, Node* newParent) {
10        Node* oldParent = node->parent;
11        node->parent = newParent;
12
13        // Clean up the child if it's the new parent
14        if (node->left == newParent)
15            node->left = nullptr;
16        if (node->right == newParent)
17            node->right = nullptr;
18
19        // If it's original root, then we're done
20        if (node == root)
21            return node;
22
23        // Move the left child to the right if it's not the new parent
24        if (node->left)
25            node->right = node->left;
26        node->left = reroot(root, oldParent, node);
27
28        return node;
29    }
30};

C# Solution:

1
2cpp
3Public class Solution {
4    public Node FlipBinaryTree(Node root, Node leaf) {
5        return Reroot(root, leaf, null);
6    }
7
8    private Node Reroot(Node root, Node node, Node newParent) {
9        Node oldParent = node.Parent;
10        node.Parent = newParent;
11
12        // Clean up the child if it's the new parent
13        if(node.Left == newParent)
14            node.Left = null;
15        if(node.Right == newParent)
16            node.Right = null;
17
18        // If it's original root, then we're done
19        if(node == root)
20            return node;
21
22        // Move the left child to the right if it's not the new parent
23        if(node.Left != null)
24            node.Right = node.Left;
25        node.Left = Reroot(root, oldParent, node);
26
27        return node;
28    }
29}

In all the solutions provided above we are first checking if the node's child is equal to NewParent(node which we would like to make parent), if yes then we are cleaning up the child (making it none). If node is equal to root node which was the original root then just return node as we are done. If node's left child is not equal to NewParent then change it to right child and then changing left child to parent node (making current node it's parent). These changes are done because we have to make leaf node as root and all other remaining nodes as its child nodes starting from it's parent make it left child, and it's sibling(if any) as right child.To make the entire rebalancing process clearer, consider this scenario: We have a node with its left child and right child. To flip the binary tree, we want to make sure that all the references are correctly updated. For every node, we make its parent the new left child and its left child the new right child. This is the essence of the solution above.

Complexity Analysis:

The time complexity of the solution is O(n), where n is the number of nodes in the binary tree. This is because we may have to visit all nodes in the worst-case scenario.

The space complexity is also O(n), due to the depth of the recursion call stack, which could, in the worst case, equal the height of the binary tree.

Testing the Solutions:

To make sure that your solution works, you can prepare a set of test cases including edge cases, and run the solution on these test cases. A good set of test cases might include:

• A test case with a binary tree of only one node. The solution output must equal the input binary tree.
• A test case with a binary tree of 3 nodes: root, left child, right child. Regardless of the chosen leaf, the result must be a valid binary tree.
• A case with more complex binary tree configuration, such as the example provided in the problem statement.

Conclusion:

Changing the root of a binary tree is a task that involves careful manipulation of the tree's nodes. By using a depth-first search algorithm that updates the parent and children of each node, we can successfully reroot the tree with a new root node. This solution is efficient, with linear time and space complexity, and can be implemented in different programming languages like Python, Java, Javascript, C#, and C++.

Always challenge your solution by running several test cases to ensure its accuracy and efficiency. Happy coding!