Invert Binary Tree
Understand the problem
Given the root of a binary tree.
Invert the tree — swap the left and right children at every node — and return the root.
ts
class TreeNode {
val: number
left: TreeNode | null
right: TreeNode | null
}
// 4 4
// / \ / \
// 2 7 → 7 2
// / \ / \ / \ / \
// 1 3 6 9 9 6 3 1Inverting a tree is a classic recursion exercise: at each node, swap the two children, then keep inverting the two subtrees.
It's a form of depth-first traversal (DFS).
Optimal solution
Optimal
O(n) time, O(h) space (h is the tree height, from the recursion stack)ts
function invertTree(root: TreeNode | null): TreeNode | null {
if (!root) return null
// Invert both subtrees first, then swap them
const left = invertTree(root.left)
const right = invertTree(root.right)
root.left = right
root.right = left
return root
}Key insight:
Depth-first recursion is the optimal approach: invert the left and right subtrees, then swap the two children at the current node.
- Every node is visited exactly once → O(n).
- The extra memory is the depth of the recursion stack: O(n) in the worst case for a skewed tree, O(log n) in the best case for a balanced tree.
Step-by-step trace
Step through the run — click a step to see its line of codeOpen the interactive visualizer
1function invertTree(root: TreeNode | null): TreeNode | null {2 if (!root) return null3 4 // Invert both subtrees first, then swap them5 const left = invertTree(root.left)6 const right = invertTree(root.right)7 root.left = right8 root.right = left9 10 return root11}Edge cases to remember
root = null (empty tree) → return null immediately.
A single node → no children to swap → return itself.
Completely one-sided tree (only left children) → after inverting, the branch moves to the right children.
Full balanced tree → every pair of children is swapped.