Invert Binary Tree
Swap children at every node.
Recursive Inversion, Step by Step
Problem
Given the root of a binary tree, modify the tree so that it becomes its mirror image. At every node, exchange the references to its left and right children, then apply the same transformation to both resulting subtrees. Return the root of the transformed tree.
Examples
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Input: root = [2,1,3]
Output: [2,3,1]
The Goal
Turn the tree into its mirror image: at every node, the left and right children trade places. Return the root.
For [4,2,7,1,3,6,9], the result is [4,7,2,9,6,3,1]. The root keeps its value. Its two subtrees swap sides, and so do the children inside them.
Swap pointers, not values
Each node keeps its value. Only its left and right pointers trade, and each pointer brings its whole subtree along.
Mirror every node, all the way down.
Key Idea: One Swap per Node
Mirroring a tree is the same small job at every node: swap its two child pointers.
Swapping at the root moves both subtrees whole, but their insides aren't mirrored yet. So after the swap, invert each subtree the same way. An empty child is already its own mirror, which ends the recursion.
At 7, left 6 and right 9 become left 9 and right 6.
The Algorithm
def invert_tree(node):
if node is None:
return None
node.left, node.right = node.right, node.left
invert_tree(node.left)
invert_tree(node.right)
return nodeThe swap comes before the recursive calls, so node.left is already the old right subtree. Either order of the two calls gives the same tree. A queue or a stack works too: visit every node once and swap.
| Approach | Worklist | Extra space |
|---|---|---|
| Recursive DFS | Call stack | O(h) |
| Iterative DFS | Stack | O(h) |
| BFS | Queue | O(w), w the widest level |
Walkthrough
Run it on [4,2,7,1,3,6,9].
At 4, the swap puts 7 on the left and 2 on the right. The recursion follows the new left pointer to 7 and swaps 6 and 9. Leaves 9 and 6 swap two empty children, which changes nothing.
Back at 4, it goes right to 2 and swaps 1 and 3. Every node has swapped once: [4,7,2,9,6,3,1].
Checkpoint · predict the next step
Step 9 of 29 on the stage: Both of 9's subtrees are mirrored. Return 9.
node on 9 · call stack = [invert_tree(4), invert_tree(7), invert_tree(9) → 9]
Pitfalls
- Swap the pointers, not the values. Swapping the values 1 and 3 leaves their subtrees where they were.
- Recurse into both children. Inverting one side leaves the other unmirrored.
- Swap in one statement, or save a pointer first.
node.left = node.righton its own loses the left subtree. - An empty tree returns
None. A symmetric tree like[1,2,2,3,4,4,3]comes back unchanged.
Node 2 has left child 1 and right child 3, each with children of its own. What does inverting at 2 do?
Complexity
Each node is visited once and does one swap, so time is O(n).
The tree changes in place, so the only extra space is the call stack: one call per level of the current path, O(h). That's O(log n) for a balanced tree and O(n) for a chain.
One swap per node
- Visit every nodeOnce each.dominantO(n)
- Swap two pointersPer node.O(1)
- Call stackAs deep as the tree.O(h)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(n) | 10 | 100 | 1K | 10K |
Every node has to swap, so linear time is as fast as it gets.
In short
Recursively (or with a stack/queue) visit each node and swap its left and right children. DFS or BFS both work since you touch every node exactly once. The recursion bottoms out at nulls.
Common mistake
Swapping values instead of the child pointers, or forgetting to recurse into both subtrees.