156. Binary Tree Upside Down

MediumTreeDepth-First SearchBinary Tree
Leetcode Link

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:

  1. The leftmost child becomes the new root of the tree.
  2. The parent of this new root becomes its right child.
  3. 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.

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which of these properties could exist for a graph but not a tree?

Solution Approach

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

  1. 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.

  2. 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.

    1new_root = self.upsideDownBinaryTree(root.left)

  3. 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.

    1root.left.right = root
2root.left.left = root.right

  4. 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.

    1root.left = None
2root.right = None

  5. 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.

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

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

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:

1    1
2   / \
3  2   3
4 / \
54   5

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:

  1. 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.

  2. 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:

14
2 \
3  2
4   \
5    5

  1. Node '2' is now a child, so its original connections to '4' and '5' should be broken.

  2. 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'.

  3. The connections from node '1' to its children are severed as well. The tree now looks like this:

1    4
2     \
3      2
4     / \
5    3   1
  1. 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
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

Binary Tree Min Depth

Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ