Trees · LC #226
Invert Binary Tree
Mirror a binary tree by swapping left and right children at every node. A single recursive post-order (or pre-order) DFS achieves this in O(n) time.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given the root of a binary tree, invert the tree (create its mirror image) and return its root.
Sample I/O
Input: 4 Output: 4
/ \ / \
2 7 7 2
/ \ / \ / \ / \
1 3 6 9 9 6 3 1Time: O(n) · Space: O(h)
Intuition
How to Think About It
Intuition
Recursion works because inverting a tree is equivalent to swapping children at every node independently - a perfect sub-problem decomposition. Each call only needs to invert its own two subtrees and then swap them.
Core Concept
At each node: recursively invert both subtrees, then swap `root.left` and `root.right`. The swap can also happen before recursing (pre-order) - both orderings produce the same result. Base case: null → return null.
When to use
When you need to mirror/reflect a binary tree, or as a sub-step in symmetry checks.
When NOT to use
Not applicable to BSTs where you need to preserve sorted order - inverting destroys BST property.
Key Insights
What to Know Cold
- Swap can happen before or after recursing - both yield correct result.
- BFS (level-order) alternative: enqueue nodes and swap children as each is dequeued.
- Inverting twice returns the original tree.
- The operation modifies the tree in-place; original references are updated.
- Null base case ensures leaves work correctly without explicit leaf detection.
1 example
Worked Examples
Four-level tree inversion
Tree rooted at 4 with left subtree [2,1,3] and right [7,6,9].
invertTree(4): invert right→[2,9,6], invert left→[7,3,1], swap children. Result: 4→[7,9,6],[2,3,1].
function invertTree(root: TreeNode | null): TreeNode | null {
if (!root) return null;
[root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
return root;
}Output: [4,7,2,9,6,3,1]
Shows the elegant one-liner destructuring swap pattern in TypeScript.