Invert Binary Tree: The Recursion Problem That Reveals How You Think
Invert a binary tree by recursively swapping left and right children — intuition, a worked walkthrough, JavaScript code, complexity, and common mistakes.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Invert Binary Tree is famous for one reason: a frustrated engineer once tweeted that Google turned him down because he "couldn't whiteboard it." The problem sounds intimidating — invert a whole tree — but the entire solution fits in four lines. What it really tests is whether you trust recursion to do the boring, repetitive work for you.
The insight is that inverting a tree is not a big operation. It's the same tiny operation — swap a node's two children — applied at every node. Once you see that, the code writes itself.
Master this and you have the template for almost every "do something at every node" tree problem: Maximum Depth, Balanced Binary Tree, Diameter. They all share this exact recursive skeleton.
The problem
Given the root of a binary tree, invert it and return the root. Inverting means producing the mirror image: at every node, the left and right subtrees swap places.
Input tree: Inverted (mirror):
4 4
/ \ / \
2 7 -> 7 2
/ \ / \ / \ / \
1 3 6 9 9 6 3 1Read the leaves left to right: the original is 1 3 6 9, the mirror is 9 6 3 1 — reversed, exactly as a mirror would show it. The tree in the example is given in level-order as 4,2,7,1,3,6,9, and the answer comes back as 4,7,2,9,6,3,1.
Note this is a full swap at every node, not just the top. Flipping only the root's two children would leave 1 3 and 6 9 in their original order underneath. Every node has to swap.
The brute force baseline
You might reach for a level-by-level approach with a queue (BFS), swapping children as you dequeue each node:
function invertTree(root) {
if (root === null) return null;
const queue = [root];
while (queue.length > 0) {
const node = queue.shift();
const temp = node.left;
node.left = node.right;
node.right = temp;
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
return root;
}This is correct and runs in O(n) time — it's a perfectly good answer. But it's more machinery than the problem needs: an explicit queue, a shift() that costs O(n) on a plain array, and manual null-checks before every push. The recursive version expresses the same idea with less ceremony, because the call stack is your queue for free.
The key insight
Ask the recursive question: what does it mean to invert the tree rooted at this node?
It means: swap this node's left and right children, then invert whatever subtree is now on the left, and invert whatever subtree is now on the right. That's the whole definition — recursive by nature.
The base case is trivial. Inverting a null (an empty tree, or a missing child) requires doing nothing, so you just return. Every recursion needs a stopping point, and root === null is it.
This is the DFS "solve-at-every-node" pattern: define the answer for one node in terms of the answers for its children, trust the recursion to handle the children, and let the base case unwind the stack.
The optimal solution
Here is the exact algorithm the visualizer steps through — a recursive depth-first swap:
function invertTree(root) {
if (root === null) {
return null;
}
const temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);
invertTree(root.right);
return root;
}Three moves per node:
- Base case — if the node is
null, returnnull. Nothing to invert. - Swap — exchange
root.leftandroot.rightusing atempvariable, because a directroot.left = root.rightassignment would clobber the left pointer before you saved it. - Recurse — call
invertTreeon both children. Order does not matter here; left-first and right-first both produce the same mirror.
One subtlety worth naming: after the swap, root.left already points to the former right child. So the two recursive calls descend into the newly-swapped subtrees. Because the swap at each node is independent of what happens below it, this ordering never causes a conflict.
Walkthrough
Tracing invertTree on the tree 4,2,7,1,3,6,9. Each row is one recursive frame; "swap" shows the two children exchanged at that node, and the call stack column shows what's currently unwinding.
| Step | Call stack (deepest last) | Node | Swap performed | Nodes swapped so far |
|---|---|---|---|---|
| 1 | 4 | 4 | left(2) ↔ right(7) | 1 |
| 2 | 4, 7 | 7 | left(6) ↔ right(9) | 2 |
| 3 | 4, 7, 9 | 9 | left(null) ↔ right(null) | 3 |
| 4 | 4, 7, 6 | 6 | left(null) ↔ right(null) | 4 |
| 5 | 4, 2 | 2 | left(1) ↔ right(3) | 5 |
| 6 | 4, 2, 3 | 3 | left(null) ↔ right(null) | 6 |
| 7 | 4, 2, 1 | 1 | left(null) ↔ right(null) | 7 |
The order tells the story. Node 4 swaps first, putting 7 on the left. The recursion then dives into 7 (step 2), swaps its children, and keeps going down the left spine — 9 and 6 — before it ever touches the 2 subtree. Only after 7's entire subtree is inverted does the stack unwind back to 4 and descend right into 2 (step 5). Leaves like 9, 6, 3, and 1 "swap" two nulls, which is a no-op, but the visit still counts. After 7 frames, all 7 nodes are done and the tree reads 4,7,2,9,6,3,1.
Complexity
| Metric | Value | Why |
|---|---|---|
| Time | O(n) | Each of the n nodes is visited exactly once; the swap is O(1) constant work |
| Space | O(h) | The recursion stack holds one frame per level; h is the tree height |
The height h ranges from O(log n) for a balanced tree to O(n) for a fully skewed one (a linked-list-shaped tree), so worst-case space is O(n). That stack space is the only cost the iterative BFS version trades for an explicit queue — same time, same asymptotic space.
Common mistakes
- Skipping the
tempvariable. Writingroot.left = root.right; root.right = root.left;overwrites the left pointer before you save it, so both children end up pointing at the original right subtree and the left is lost. You need the temp to hold one side during the swap. - Only swapping the root's children. Inversion is recursive. If you swap at the top and forget to recurse, the deeper levels keep their original order and the tree is only half-mirrored.
- Forgetting the null base case. Without
if (root === null) return, the first leaf'snullchild triggers aCannot read property 'left' of nullcrash. The base case is what lets the recursion terminate cleanly. - Swapping the values instead of the pointers. Copying
node.valbetween children works for the root but breaks the moment subtrees have different shapes — a left subtree of 3 nodes and a right subtree of 1 can't have their values swapped position-for-position. Swap the child references, not the payload.
Where this pattern shows up next
The "do one O(1) thing at every node, recurse into both children" skeleton is the backbone of nearly every basic tree problem. Once inversion clicks, these are variations on the same call structure:
- Maximum Depth of Binary Tree — same recursion, but you combine child results (
1 + max(left, right)) instead of swapping them. - Maximum Depth of Binary Tree - Top Down — the same depth answer computed by passing state down the tree rather than returning it up.
- Balanced Binary Tree — recurse for heights, then check the left/right difference at every node.
- Diameter of Binary Tree — track left and right depths per node and combine them into a global maximum.
To watch the swaps fire and the call stack grow and unwind frame by frame, step through Invert Binary Tree in the visualizer.
FAQ
What does it mean to invert a binary tree?
Inverting a binary tree means producing its mirror image: at every node, the left and right children swap positions, all the way down. If you held the original tree up to a mirror, what you'd see is the inverted tree — the leftmost leaf becomes the rightmost, and so on. It is not a value sort or a rebalancing; the structure is preserved and only the left/right orientation flips at each node.
Why is Invert Binary Tree solved with recursion?
Because the operation is self-similar. Inverting a tree is defined in terms of inverting its two subtrees, which is the exact shape recursion handles best. You swap the current node's children, then let recursion invert each subtree the same way. The base case — an empty node — stops the descent. You can solve it iteratively with a queue or stack, but the recursive form mirrors the problem's own definition, so it's shorter and clearer.
What is the time and space complexity of inverting a binary tree?
Time is O(n), where n is the number of nodes, because each node is visited exactly once and the per-node swap is constant work. Space is O(h), where h is the tree's height, from the recursion call stack. For a balanced tree that's O(log n); for a completely skewed tree it degrades to O(n). The iterative BFS version has the same time and asymptotic space, just with an explicit queue instead of the call stack.
Do the two recursive calls need to happen in a specific order?
No. Whether you recurse into the left child first or the right child first, every node still gets its children swapped exactly once, and the final mirror is identical. The swap at each node is independent of the work done in its subtrees, so the traversal order (pre-order left-first, as in the standard solution, or right-first) has no effect on correctness — only on the sequence of steps you'd see in a trace.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.