Invert Binary Tree: The Famous Three-Line Solution

You are given the root of a binary tree. Swap every node's left and right children, all the way down, so the tree becomes a mirror image of itself.

This is LeetCode 226: Invert Binary Tree, and it might be the most famous easy problem on the entire site. Not because it is hard. Because of a tweet.

In 2015, Max Howell (the creator of Homebrew, the package manager used by millions of developers) tweeted that Google rejected him in an interview because he could not invert a binary tree on a whiteboard. The internet lost its mind. The meme has lived on ever since, and "invert a binary tree" became shorthand for the gap between real-world engineering and whiteboard interviews.

The irony? The solution is genuinely three lines of code. Let's walk through it.

Why this problem matters

Invert Binary Tree is not just a meme. It is a perfect introduction to tree recursion because the operation is so visual. You can look at the before and after and immediately see what happened: every left child became a right child and vice versa, at every single level.

That clarity makes it a great place to build your intuition for how recursive tree transformations work. Unlike problems where you compute a value (like maximum depth), here you are actually modifying the tree structure. The recursive pattern is the same, but the "combine" step is a swap instead of a comparison.

The key insight

At every node, you just need to do one thing: swap the left and right children. Then do the same thing for the left subtree and the right subtree. That is it. The recursion handles visiting every node for you.

Think about it like flipping a mirror. You flip the top level, then flip each subtree, and each sub-subtree, all the way down. When you hit a null node, there is nothing to flip, so you stop.

The recursive 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

Three lines of real logic. Let's break them down:

• if root is None: return None is the base case. If the node does not exist, there is nothing to invert. This is where every recursive path eventually terminates.
• root.left, root.right = root.right, root.left is the swap. Python's tuple assignment makes this a single line. We swap the two children of the current node before recursing.
• invert_tree(root.left) and invert_tree(root.right) recurse into both subtrees, inverting everything below.

The order matters here. We swap first, then recurse. This is a pre-order traversal: process the current node, then visit left, then visit right. You could also do the swap after recursing (post-order) and it would work just as well, because the swap at each node is independent of the swaps in its subtrees.

Visual walkthrough

Let's trace the recursion through the tree [4, 2, 7, 1, 3, 6, 9] step by step. Watch how each node swaps its children before recursing deeper.

Notice how the recursion works top-down. Node 4 swaps first, then we recurse into its (now-swapped) left child 7, which swaps its children 9 and 6. After the left subtree is fully inverted, we move to the right child 2, which swaps 3 and 1. Every node only needs to worry about swapping its own two children. The recursion takes care of the rest.

The iterative BFS solution

You can also solve this with BFS using a queue. Instead of recursing, you process nodes level by level and swap each node's children as you visit it.

from collections import deque

def invert_tree(root):
    if root is None:
        return None
    queue = deque([root])
    while queue:
        node = queue.popleft()
        node.left, node.right = node.right, node.left
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return root

The BFS version visits every node exactly once, swapping its children along the way. It does not matter what order you visit the nodes in. Every node's swap is independent, so BFS, DFS pre-order, or DFS post-order all produce the same result.

The recursive version is shorter and more elegant. The BFS version avoids recursion and uses explicit memory (the queue) instead of the call stack. For this problem, either approach works well.

Complexity analysis

Time is O(n) for both approaches. You visit every node exactly once and do O(1) work (a swap) at each node.

Space depends on the tree shape. The DFS recursive solution uses O(h) stack space where h is the height of the tree. For a balanced tree, h = log n. For a completely skewed tree (basically a linked list), h = n.

The BFS solution uses O(w) space where w is the maximum width of any level. For a balanced tree, the widest level has up to n/2 nodes, so the queue holds O(n). For a skewed tree, each level has one node, so the queue holds O(1).

In practice, the recursive DFS solution is the standard answer for this problem. It is concise, easy to remember, and the stack depth is never an issue with typical LeetCode constraints.

Edge cases to watch for

• Empty tree (root is None): return None. The base case handles this.
• Single node (no children): return the node unchanged. The swap is None, None = None, None, which is a no-op.
• Skewed tree (every node has only one child): the recursion still works. Each node swaps its one child to the other side. The result is a mirror-image linked list.
• Already symmetric tree: inverting a symmetric tree produces the same tree. The algorithm does not check for this and that is fine.

The building blocks

This problem uses two fundamental building blocks:

1. Recursive null base case (recursive-null-base). The skeleton of "if null, return; otherwise process and recurse into children" is the same pattern used in Maximum Depth, Same Tree, Validate BST, and many more. The base value here is None (nothing to transform), rather than 0 (nothing to count).

2. Pre-order state passing (pre-order-state-passing). We do the work (swapping children) at the current node before recursing into the subtrees. This is a pre-order traversal: process, then go left, then go right. The "state" we are passing down is the structural change (the swap), which each node applies to itself before letting its children do the same.

# The general pattern:
def solve(node):
    if node is None:
        return None           # recursive-null-base
    # do work at current node  # pre-order-state-passing
    solve(node.left)
    solve(node.right)
    return node

For Invert Binary Tree, "do work" means swapping left and right children. For other problems, it might mean collecting a value, checking a condition, or modifying a property. The skeleton stays the same.

From understanding to recall

You just traced through a three-line recursive solution and saw exactly how each node swaps its children. It makes sense right now. But will you be able to reproduce it from memory in two weeks when an interviewer asks for it? Or when you see a similar tree transformation problem and need to apply the same pattern?

Understanding is not recall. You understood the solution. Recall means you can write it from scratch, under pressure, without looking anything up.

Spaced repetition builds recall. You practice typing the solution from memory at increasing intervals. First after a day, then three days, then a week. Each time, you reconstruct the base case, the swap, and the recursive calls. After a few reps, the recursive null base case pattern with pre-order processing becomes automatic.

These two building blocks (recursive-null-base and pre-order-state-passing) show up in dozens of LeetCode tree problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Maximum Depth of Binary Tree - Uses the exact same recursive null base case pattern, but computes a value instead of transforming the tree
• Number of Islands - Another recursive DFS problem where you modify the structure (marking visited cells) as you traverse
• Reverse Linked List - A similar "reverse/invert a data structure" problem that builds the same recursive intuition on a simpler structure