LeetCode 156: Binary Tree Upside Down

Problem Restatement

We are given the root of a binary tree.

We need to flip the tree upside down and return the new root.

The transformation follows these rules:

1. The original left child becomes the new root of that local subtree.
2. The original root becomes the new right child.
3. The original right child becomes the new left child.

The operation is done level by level.

The input has an important guarantee: every right node has a sibling and has no children. In older wording, all right nodes are either leaf nodes with a left sibling or empty. This guarantee makes the flip well-defined.

Input and Output

Example function shape:

def upsideDownBinaryTree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    ...

Example

Input tree:

    1
   / \
  2   3
 / \
4   5

Level-order form:

[1, 2, 3, 4, 5]

After flipping:

    4
   / \
  5   2
     / \
    3   1

Level-order form:

[4, 5, 2, None, None, 3, 1]

The old leftmost node 4 becomes the new root.

The old right child 5 becomes the left child of 4.

The old parent 2 becomes the right child of 4.

Then the same pattern continues upward.

First Thought: Understand One Local Flip

Consider a small tree:

  root
  /  \
 L    R

After flipping this local shape:

   L
  / \
 R   root

So the pointer changes are:

L.left = R
L.right = root
root.left = None
root.right = None

For a full tree, we apply this from the bottom of the left spine upward.

That means recursion is natural: first flip the left subtree, then rewire the current root below its left child.

Key Insight

The new root is always the leftmost node of the original tree.

For example:

    1
   /
  2
 /
4

After flipping, 4 becomes the root.

So recursion should go left until it reaches the leftmost node.

Base case:

if root is None or root.left is None:
    return root

Then as recursion returns, each old parent is attached as the right child of its old left child.

Algorithm

Use recursive DFS.

For each node root:

1. If root is empty or has no left child, return root.
2. Recursively flip root.left.
3. Let the original left child receive new children:
   • root.left.left = root.right
   • root.left.right = root
4. Clear the old root pointers:
   • root.left = None
   • root.right = None
5. Return the new root from the recursion.

Walkthrough

Use:

    1
   / \
  2   3
 / \
4   5

Start at 1.

Before flipping 1, we first flip its left subtree rooted at 2.

At node 2, before flipping it, we first flip its left subtree rooted at 4.

Node 4 has no left child, so it becomes the new root.

Now unwind to node 2.

Original local shape:

  2
 / \
4   5

Rewire:

4.left = 5
4.right = 2
2.left = None
2.right = None

Now we have:

  4
 / \
5   2

Then unwind to node 1.

Original local shape around 1:

  1
 / \
2   3

Now 2 is already below 4, but it is still the old left child of 1.

Rewire:

2.left = 3
2.right = 1
1.left = None
1.right = None

Final tree:

    4
   / \
  5   2
     / \
    3   1

Correctness

The algorithm reaches the leftmost node first. That node has no left child, so it must become the new root after the upside-down transformation.

Now consider any original node root with left child L and right child R.

By the time recursion returns to root, the subtree rooted at L has already been flipped correctly, and L is positioned as the place where root should be attached.

The required local transformation says:

L.left = R
L.right = root

The algorithm performs exactly these assignments:

root.left.left = root.right
root.left.right = root

Then it clears:

root.left = None
root.right = None

This prevents old pointers from forming cycles.

Because the algorithm performs the correct local transformation for every node on the left spine, from bottom to top, the entire tree is flipped correctly.

Complexity

Let n be the number of nodes and h be the height of the tree.

Implementation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None or root.left is None:
            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

Code Explanation

The base case handles an empty tree or a node with no left child:

if root is None or root.left is None:
    return root

A node with no left child becomes the top of the flipped subtree.

This line flips the left subtree first:

new_root = self.upsideDownBinaryTree(root.left)

After that call returns, new_root is the leftmost node of the original subtree.

Now we rewire the old left child:

root.left.left = root.right
root.left.right = root

The old right child becomes the new left child.

The old root becomes the new right child.

Then we remove the old links:

root.left = None
root.right = None

Finally, we return the same new root all the way up:

return new_root

Iterative Version

We can also do the same transformation while walking down the left spine.

class Solution:
    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        prev_root = None
        prev_right = None

        while root:
            next_root = root.left
            next_right = root.right

            root.left = prev_right
            root.right = prev_root

            prev_root = root
            prev_right = next_right
            root = next_root

        return prev_root

Here:

This version uses constant extra space.

Testing

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def level_order(root):
    if not root:
        return []

    q = [root]
    out = []

    while q:
        node = q.pop(0)

        if node:
            out.append(node.val)
            q.append(node.left)
            q.append(node.right)
        else:
            out.append(None)

    while out and out[-1] is None:
        out.pop()

    return out

def run_tests():
    sol = Solution()

    root = TreeNode(
        1,
        TreeNode(2, TreeNode(4), TreeNode(5)),
        TreeNode(3),
    )

    new_root = sol.upsideDownBinaryTree(root)
    assert level_order(new_root) == [4, 5, 2, None, None, 3, 1]

    assert sol.upsideDownBinaryTree(None) is None

    single = TreeNode(1)
    assert level_order(sol.upsideDownBinaryTree(single)) == [1]

    root = TreeNode(1, TreeNode(2), TreeNode(3))
    assert level_order(sol.upsideDownBinaryTree(root)) == [2, 3, 1]

    print("all tests passed")

run_tests()