156. Binary Tree Upside Down

Problem Description

The problem deals with a unique operation on a binary tree named 'upside down transformation.' To understand this transformation, imagine the binary tree made of a set of top-down connected left nodes. The following steps will guide you through this transformation:

The leftmost child becomes the new root of the tree.
The parent of this new root becomes its right child.
The sibling of the new root, which is the original right node, becomes its left child.

This process is then applied recursively to the subtree rooted at the new root (which was the left child of the original tree). What's important to note here is that every right node in the binary tree is always a leaf and has a sibling, which ensures the consistency of the transformation.

Here is what happens during the transformation:

We start with the leftmost node since it will become the new root.
We recursively transform the subtree rooted with this node as described.
We change the pointers of the parent and the sibling to fulfill the requirements of the upside down transformation.

The goal of the exercise is to return the new root after this transformation.

Flowchart Walkthrough

Certainly! Here's the analysis of using the algorithm flowchart for Leetcode 156. Binary Tree Upside Down:

Let's break down the solution strategy step-by-step using the Flowchart:

Is it a graph?

Yes: A binary tree is a specialized graph where each node has at most two children.

Is it a tree?

Yes: The problem specifically involves a binary tree.

DFS

Reaching this node indicates that Depth-First Search is appropriate for the problem.

Conclusion: Following the flowchart, DFS is the correct approach for this tree-related problem, given that the structure of the binary tree is critical to the inversion process required by the problem.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The transformation process naturally lends itself to a recursive approach. By following the recursive tree traversal, we can handle the reconfiguration from the bottom up, which avoids dealing with incomplete or inconsistent states.

Here's the intuition behind the solution:

If the current node is null or it doesn't have a left child, we have reached a base case where nothing needs to change; simply return the current node.
We apply the transformation to the left subtree and keep the new root returned by the recursive function call.
Knowing that the transformation rules should apply to one level at a time, we now handle the parent (current root) and its children (leaves, in this context). We attach the parent to the right of the leftmost child which is now the new root and attach the sibling (right child of the root) to its left.
Finally, the original root's left and right children should point to null to complete the transformation for the current level.

By continuously applying this logic, we process all levels of the tree until we reach the new root, which is then returned.

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

Solution Approach

The solution to the problem uses a recursive algorithm that follows the depth-first search pattern:

The algorithm starts at the root of the binary tree and checks if it's needed to proceed with the transformation. If root is None or root.left is None, it indicates that we've either reached the end of a branch or a node that doesn't have a left child (and hence, cannot be flipped). In this case, the root itself is returned.
Once we confirm that there is a left child to process, we call the same function recursively with the left child of the current root. The expectation is that this call will return the new root for the entire subtree that's rooted at root.left.
```
new_root = self.upsideDownBinaryTree(root.left)
```
After the recursive call returns the new_root, which is the leftmost child now acting as the root of the upside down subtree, we must assign the original root as the right child and the original right child as the left child of the new_root.
```
root.left.right = root
root.left.left = root.right
```
Once the reassignment of children is done, it's important to detach the original root from its children to prevent cycles and to reflect that it is now a child node without further children.
```
root.left = None
root.right = None
```
Finally, we know that the new_root has gone through the necessary transformations and has the rest of the tree (that we're not currently looking at) correctly configured. Hence, new_root is returned, which, on the final return, will be the new root of the completely transformed tree.

Here's how to visualize the algorithm at every recursive step:

Identify the leftmost node that will become the new root.
Make the parent a child of this new root by updating the relevant pointers.
Remove the parent’s original connections.

This recursive approach is efficient because it takes O(n) time due to visiting each node once. It’s important to note that a recursive approach is managed via the call stack, which could potentially lead to stack overflow on extremely deep trees, although this issue is not common.

This pattern is a particular instance of "tree traversal", where you usually visit each node and perform an operation. In this case, the operation involves changing the pointers within the tree.

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 binary tree to understand the solution step by step. Imagine we have a binary tree as follows, represented in its original state:

Here, '1' is the root, '2' is its left child, '3' is its right child, and so on. According to our 'upside down' transformation rules, '4' will become the new root. The steps of the transformation would be:

Using recursion, we go all the way to the leftmost child, which in our example is node '4'. As there are no more left children, this node will be returned as the new_root.
On the way back up the recursion, we now consider node '2' as the original root with node '4' being the new_root returned from the previous recursive call.
- We transform node '2' so that it becomes the right child of node '4' (since node '4' is the leftmost child and is therefore the new root of the subtree).
- We assign the original right child of node '2', which is node '5', to be the left child of node '4'.
After this step, the tree under '4' looks like this:

Node '2' is now a child, so its original connections to '4' and '5' should be broken.
The recursion then considers node '1' with the new_root being node '4'.
- Node '1' now becomes the right child of node '2'.
- The original right child of node '1', which is node '3', becomes the left child of node '2'.
The connections from node '1' to its children are severed as well. The tree now looks like this:

The recursion ends as we have traversed all nodes. The new_root (node '4') is returned.

The tree has been completely transformed, according to our rules, and the new structure has been achieved via several recursive calls, each modifying the structure according to the 'upside down' rules defined.

Solution Implementation

1# Class definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val        # Node's value
5        self.left = left      # Left child
6        self.right = right    # Right child
7
8class Solution:
9    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
10        # Base case: if the root is None or the root doesn't have a left child,
11        # the tree cannot be flipped, so return the root as is.
12        if root is None or root.left is None:
13            return root
14
15        # Recursive case: dive into the left subtree to find the new root after flipping.
16        new_root = self.upsideDownBinaryTree(root.left)
17
18        # Once the recursion unwinds, the original root's left child's right child
19        # becomes the original root (making the left child the new parent).
20        root.left.right = root
21
22        # The left child's left child becomes the original root's right child.
23        root.left.left = root.right
24
25        # Erase the original root's left and right children, since they've been reassigned.
26        root.left = None
27        root.right = None
28
29        # Return the new root of the flipped tree.
30        return new_root
31

1class Solution {
2  
3    /**
4     * Transforms a given binary tree to an upside-down binary tree.
5     * In the upside-down version, the original left child becomes the new root,
6     * the original root becomes the new right child, and the original right child 
7     * becomes the new left child.
8     *
9     * @param root The root of the binary tree to be transformed.
10     * @return The new root of the upside-down binary tree.
11     */
12    public TreeNode upsideDownBinaryTree(TreeNode root) {
13        // Base case: if the tree is empty or the root has no left child,
14        // the tree does not change.
15        if (root == null || root.left == null) {
16            return root;
17        }
18      
19        // recursively call the function on the left subtree.
20        // This recursive call goes down to the leftmost child and this node
21        // will become the new root of the upside down tree.
22        TreeNode newRoot = upsideDownBinaryTree(root.left);
23      
24        // The current root's left child's right subtree becomes
25        // the current root (One level up).
26        root.left.right = root;
27      
28        // The current root's right child becomes the new left child
29        // of current root's left child.
30        root.left.left = root.right;
31      
32        // The current root's left and right children are set to null
33        // because they have been moved up the tree.
34        root.left = null;
35        root.right = null;
36      
37        // Return the new root, which is the leftmost child of the original tree.
38        return newRoot;
39    }
40  
41    /**
42     * Definition for a binary tree node.
43     */
44    public class TreeNode {
45        int val;
46        TreeNode left;
47        TreeNode right;
48      
49        TreeNode() {}
50      
51        TreeNode(int val) {
52            this.val = val;
53        }
54      
55        TreeNode(int val, TreeNode left, TreeNode right) {
56            this.val = val;
57            this.left = left;
58            this.right = right;
59        }
60    }
61}
62

1// Definition for a binary tree node.
2struct TreeNode {
3    int val;
4    TreeNode *left;
5    TreeNode *right;
6  
7    // Constructor to initialize the node with a value and optional children
8    TreeNode(int x = 0, TreeNode *left = nullptr, TreeNode *right = nullptr) 
9        : val(x), left(left), right(right) {}
10};
11
12class Solution {
13public:
14    // This function converts a given binary tree to an "upside down" binary tree
15    // where the original left child becomes the new root.
16    TreeNode* upsideDownBinaryTree(TreeNode* root) {
17        // If the root is null or the left child is null, return the root itself because
18        // no further processing is required (end of the branch or tree is empty).
19        if (!root || !root->left) return root;
20
21        // Recursively call function on the left child to handle subtrees and
22        // to find the new root of the entire tree.
23        TreeNode* newRoot = upsideDownBinaryTree(root->left);
24
25        // The original root becomes the right child of its left child,
26        // as per the "upside down" transformation.
27        root->left->right = root;
28
29        // The original right child becomes the left child of the new parent,
30        // which is the original left child of the root.
31        root->left->left = root->right;
32
33        // The original root should not have any left or right children now,
34        // so both are set to nullptr.
35        root->left = nullptr;
36        root->right = nullptr;
37
38        // Return the new root, which is at the bottom-left of the original tree.
39        return newRoot;
40    }
41};
42

1// Type definition for a binary tree node.
2type TreeNode = {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6};
7
8// Function that creates a new TreeNode with default values.
9const createTreeNode = (val: number, left: TreeNode | null = null, right: TreeNode | null = null): TreeNode => {
10    return { val, left, right };
11};
12
13// Function to convert a given binary tree to an "upside down" binary tree
14// where the original left child becomes the new root.
15const upsideDownBinaryTree = (root: TreeNode | null): TreeNode | null => {
16    // If the root is null or the left child is null, return the root itself because
17    // no further processing is required (it's the end of the branch or the tree is empty).
18    if (!root || !root.left) return root;
19
20    // Recursively call the function on the left child to handle subtrees and
21    // to determine the new root of the entire tree.
22    const newRoot: TreeNode | null = upsideDownBinaryTree(root.left);
23
24    // The current root's left child's right child is set to the current root,
25    // following the rules of "upside down" transformation.
26    if (root.left) root.left.right = root;
27
28    // The current root's left child's left child is set to the current root's right child.
29    if (root.left) root.left.left = root.right;
30
31    // The current root should not have any left or right children now,
32    // so both are set to null.
33    root.left = null;
34    root.right = null;
35
36    // The new root, which is the leftmost leaf node of the original tree, is returned.
37    return newRoot;
38};
39

Time and Space Complexity

The given Python function upsideDownBinaryTree recursively transforms a binary tree into an upside-down binary tree as defined in a specific problem description.

Time Complexity:

The recursion visits each node exactly once. Therefore, the time complexity of the algorithm is based on the number of nodes n in the binary tree. Since each call processes constant time work excluding the recursive calls, the overall time complexity can be described as O(n).

Space Complexity:

The space complexity of the algorithm is O(h), where h is the height of the binary tree. This is due to the recursive call stack. In the worst case, if the tree is completely unbalanced (e.g., a linked list form), the height of the tree would be n, making the space complexity degenerate to O(n). In a balanced tree, the height h would be log(n), leading to a space complexity of O(log(n)).

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:

How does quick sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Quick sort does not use divide and conquer

I don't know