Invert Binary Tree

Invert a Binary Tree is a tiny problem with a famous backstory — and it is the cleanest possible introduction to tree recursion. The whole solution is three meaningful lines.

The slow way first

You might reach for something elaborate — copy the tree, walk it with explicit coordinates, rebuild it flipped. But there is no shortcut needed and nothing to optimize away: you must touch every node exactly once to swap its children, so any correct solution is already O(n). The only real question is how to express it cleanly. Recursion makes it almost trivial.

The idea: swap, then recurse

A binary tree is self-similar: each child is itself the root of a smaller binary tree. So define the job in terms of itself.

At the current node, do two things: swap its left and right child, then invert each child's subtree the same way. The base case is an empty node (None) — there is nothing to swap, so just return.

The beautiful part: because every node swaps its children, the swaps compound. The root's two whole subtrees trade sides, and inside each of those, the grandchildren trade sides too. The result is a full mirror.

Walk through it

Step through the animation. We start at the root 4 and swap its children: 2 and 7 slide past each other, dragging their entire subtrees along. Then we recurse into 7 and swap 6 ↔ 9, and into 2 and swap 1 ↔ 3. The leaves have no children, so they hit the base case and return. When every node has been visited, the bottom row reads 9, 6, 3, 1 — the original 1, 3, 6, 9 reversed.

Pseudocode

invert(node):
    if node is empty:
        return                 # base case — nothing to mirror
    swap node.left and node.right
    invert(node.left)          # mirror the (now-swapped) left subtree
    invert(node.right)         # mirror the (now-swapped) right subtree
    return node

The Python solution

def invert_tree(root):
    if root is None:
        return None
    root.left, root.right = root.right, root.left
    invert_tree(root.left)
    invert_tree(root.right)
    return root

• The if root is None check is the base case — an empty subtree needs no work, so we return immediately. It is also what stops the recursion at the leaves.
• Line 4 is the entire trick: Python tuple assignment swaps the two children in one step, no temp variable needed.
• The two invert_tree(...) calls recurse into the children. Order does not matter — after the swap, root.left is the former right child, and we mirror it too.
• We return root so callers get the (now-inverted) tree back.

Complexity

Time is O(n) — you cannot do better, since every node's children must be swapped. The extra space is O(h) for the recursion call stack, where h is the tree's height: O(log n) for a balanced tree, but O(n) in the worst case (a degenerate, list-like tree).

When this pattern shows up

Practice