Binary Tree Upside Down - Leetcode Solution

Given a binary tree, flip it upside down and turn it into a new tree where the original right nodes became left leaf nodes. Return the new root.

Example:

Input: [1,2,3,4,5]

1

/
2 3 /
4 5

Output:

4

/
5 2 /
3 1

Solution: To solve this problem, we will follow these steps:

1. If the given node is null or there is no left child for the given node, we will return the same node as it is.
2. We will recursively call the function for the left child of the given node.
3. We will set the left child of the given node as the right child of the left child of the given node.
4. We will set the right child of the given node as the left child of the given node.
5. We will set the left and the right child of the given node as null.
6. We will return the new root, which will be the left child of the original root.

Here is the Python implementation of the above approach:

class Solution:
    def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:
        if root is None or root.left is None:
            return root
        newRoot = self.upsideDownBinaryTree(root.left)
        root.left.left = root.right
        root.left.right = root
        root.left = None
        root.right = None
        return newRoot

Time Complexity: O(n)

Space Complexity: O(h), where h is the height of the binary tree.

1