Invert Binary Tree
easyTime: O(n)Space: O(h)
The shape of the problem
Return the mirror image of a binary tree: at every node, the left and right subtrees are swapped.
Signals to notice
swap left/right at every nodetree recursionnatural base case at null
Brute force first
There is no meaningfully worse brute force here — any sane approach visits every node once. The simplest is recursion; the difference is only whether you swap first or swap last.
The key insight
Inverting a tree is defined recursively: the invert of `(root, L, R)` is `(root, invert(R), invert(L))`. The base case `null → null` terminates cleanly.
Trace it on 4
/ \
2 7
/ \ / \
1 3 6 9
invert(4): recurse left(2) & right(7), then swap invert(2): recurse 1 & 3 (leaves), swap → (2, 3, 1) invert(7): recurse 6 & 9 (leaves), swap → (7, 9, 6) back at 4: swap subtrees → (4, 7, 2) with swapped children result: 4 on top, (7, 9, 6) on left, (2, 3, 1) on right
What must stay true
After invert(node) returns, the subtree rooted at node is the mirror of the original subtree.
Shape of the loop
def invert(node): if node is None: return None left = invert(node.left) right = invert(node.right) node.left, node.right = right, left return node
Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Swapping only at the root and forgetting to recurse — or recursing but not swapping. Either produces the wrong tree silently (still valid, just not mirrored).