Binary Tree Upside Down

This problem asks to flip a binary tree upside down. We can solve it using recursion.

In an upside-down version of a binary tree, the right nodes are the root nodes and the left nodes are the right leaf nodes.

The function upsideDownBinaryTree will flip the binary tree starting from the root. The new root will be the rightmost node. The left child of the current root will become the right child of the rightmost node, and the current root itself will be the left child of its own left child.

Python code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root or not root.left:
            return root

        new_root = self.upsideDownBinaryTree(root.left)
        root.left.left = root.right
        root.left.right = root
        root.left = None
        root.right = None

        return new_root

This function first checks if the root or its left child is None. If either is None, it returns the root itself, as there’s no more flipping to be done.

If the root and its left child both exist, it recursively flips the subtree starting from the left child, and sets the returned node as the new root.

Then, it updates the links of the left child of the current root and the current root itself, and sets their own left and right children to None.

Finally, it returns the new root.

This approach has a time complexity of O(n), where n is the number of nodes in the tree, as it visits each node once. The space complexity is O(h), where h is the height of the tree, as that’s the maximum depth of the recursive call stack.