Problem Statement
Invert Binary Tree
You are given a binary tree. A binary tree is a structure made of nodes, where each node holds a value and points to up to two children, one on the left and one on the right. Your job is to invert the tree, which means flipping it left to right like a mirror image. At every node, the left child and the right child swap places. When you are done, return the root, which is the top node of the tree.
Translate the prompt
Return the mirror image of a binary tree: at every node, the left and right subtrees are swapped.
Signals to notice
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).