Invert Binary Tree — The Mirror Mansion

Welcome to Dungeon 7

Six dungeons of chains: arrays, strings, linked lists. Data in a line, one thing after another.

This dungeon branches.

A binary tree is nodes and pointers, like Dungeon 6, with one upgrade that changes everything: each node points onward twice.

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

One node at the top (the root, because computer science draws trees upside down), and under it, two subtrees: left and right. And here's the sentence that unlocks the entire dungeon, read it twice: each subtree is itself a complete binary tree. The left child of the root is the root of its own smaller tree, which has its own left child rooting an even smaller tree, down to the leaves, nodes with no children at all.

A structure defined in terms of smaller versions of itself is begging to be processed by a function defined in terms of itself. That's why Dungeon 6's teaser said recursion stops being optional here. Fifteen bosses, and nearly every one is a variation of a single incantation: handle one node, trust the function to handle both subtrees.

Boss 1 is the gentlest possible version, and also the most famous.

The story

An architecture firm. A wealthy, eccentric client approved the mansion design months ago, and today she calls: "I love it. But I'm left-handed and it's all backwards. Mirror it. Everything."

The floor plan is a binary tree: every room opens onto up to two smaller rooms, a left one and a right one.

        Great Hall (4)
       /             \
   West Wing (2)   East Wing (7)
    /      \         /      \
 Study(1) Salon(3) Den(6)  Library(9)

Mirrored, the East Wing's layout must appear where the West Wing was, and inside each wing, every left/right pair flips too, down to the last closet:

        Great Hall (4)
       /             \
   East Wing (7)   West Wing (2)
    /      \         /      \
 Library(9) Den(6) Salon(3) Study(1)

The senior architects start estimating weeks of redrawing. The intern raises a hand: "A mirrored mansion is a mansion where the two wings are swapped... and each wing is itself mirrored. That's it. That's the whole spec."

Silence. Then someone says "write that down."

The problem, dressed up properly

Given the root of a binary tree, invert the tree, and return its root.

LeetCode 226. Ten words. And it comes with the best origin story in interview lore: Max Howell, author of Homebrew, the package manager half the engineers at Google use daily, tweeted in 2015 that Google rejected him because he couldn't invert a binary tree on a whiteboard. The problem has been a rite of passage ever since. Let's make sure you're never that tweet.

The naive attempt

There isn't a meaningfully worse way that still works, and that's itself a lesson: for trees, the recursive way usually is the naive way, the honest way, and the optimal way, all at once.

The genuinely naive thing people do is overthink it: build a full copy of the tree, or collect nodes into arrays by position, or try to "walk" the tree with a loop and get tangled in remembering where they've been. Loops walk chains beautifully. Trees fork, and at every fork a loop must pick one branch and somehow remember to come back for the other. That "somehow" is a stack, and recursion is the language giving you one for free.

The weapon: swap one pair, trust the recursion

Translate the intern's sentence directly:

1. Mirror of an empty plot: an empty plot. (The base case, always first.)
2. Mirror of a mansion: swap the two wings, then mirror each wing.

The hard part isn't the code. It's the trust. Every beginner stares at invert(room.left) and thinks "but I haven't written the part that handles the Study and the Salon yet". You have. It's this same function. It swaps their children and delegates deeper, until it hits empty plots and unwinds. The discipline of recursion is writing the one-node step, proving the base case, and refusing to mentally trace the rest. The machine traces; you specify.

If the trust won't come, here's the exercise that builds it, once, and then never do it again: trace a three-node tree by hand. Root swaps its two leaves. Each leaf swaps its two Nones. Done. Now believe it scales, because nothing about a bigger tree introduces a new kind of step.

Watching it work

invert(Great Hall 4)
├─ swap wings → East(7) now left, West(2) now right
├─ invert(7)
│   ├─ swap → Library(9) left, Den(6) right
│   ├─ invert(9) → swap two Nones, done
│   └─ invert(6) → swap two Nones, done
└─ invert(2)
    ├─ swap → Salon(3) left, Study(1) right
    ├─ invert(3) → done
    └─ invert(1) → done

Every node gets exactly one swap. The recursion visits each room once, mirrors it, and moves on. Nothing is copied, nothing is rebuilt, the original tree becomes its mirror.

The code

def invert_tree(root: TreeNode | None) -> TreeNode | None:
    if not root:
        return None
    root.left, root.right = root.right, root.left
    invert_tree(root.left)
    invert_tree(root.right)
    return root

Four lines of substance. In a language without tuple swap, use a temp variable, and note the swap must happen with both original pointers in hand, the same save-before-you-overwrite law that governed all of Dungeon 6.

Gotchas

1. Forgetting the base case. invert(None) must return immediately. Without the guard, the first leaf's child dereferences None and the whole mansion collapses. Base case first, always, in every boss this dungeon.

2. Swapping after recursing... into the wrong rooms. invert(root.left); invert(root.right); swap also works (post-order instead of pre-order, both fine here). What doesn't work is the half-blend: invert(root.left); swap; invert(root.left), which mirrors one wing twice and the other never. If you recurse and swap in the same function, keep straight which subtree each call is touching.

3. Building a new tree. Allocating fresh nodes gives a correct mirror and an O(n) memory bill for nothing. The swap is in-place, embrace it.

4. Only swapping the top level. Swap the wings but forget to recurse, and the mansion's first floor mirrors while every room inside stays backwards. The client notices. Clients always notice.

Complexity

Every node visited once, constant work per node.

Time: O(n). Space: O(h) where h is the tree's height, that's the recursion stack, log n for a bushy tree, n for a pathological vine.

Boss down. XP gained.

The mirrored blueprints print overnight. The client walks the halls turning left where she always wanted to, and the intern gets a permanent desk.

What you walked away with:

• Binary trees: root, left and right children, leaves, and the self-similar definition that powers everything
• The recursive incantation: base case, one node's work, trust the function on both children
• Pre-order vs post-order is just "before or after the recursive calls", and for symmetric work, either flies
• Recursion is a call stack you don't have to manage; the iterative translation always exists

Every boss from here on refines this one incantation: sometimes the one-node work is a comparison, sometimes a sum, sometimes the children's answers combine in interesting ways. The shape never changes.

Next up: Boss 2 — The Cave Survey. A caving team needs the depth of the deepest chamber, and the cave forks at every junction. The answer teaches the second half of the incantation: recursion doesn't just visit, it returns answers upward, and a parent's answer is built from its children's. One plus the deeper of two surveys.