LeetCode 226 · Easy · Trees

Invert Binary Tree

Given the root of a binary tree, mirror it: swap the left and right child of every node, then return the root.

O(n)time
O(h)space · call stack
recursionswap, then recurse

level order as on LeetCode, null = no child · up to 15 nodes, 4 levels · values −99 to 99

Call stack one frame per invertTree call · newest on the right

public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } TreeNode tmp = root.left; root.left = root.right; root.right = tmp; invertTree(root.left); invertTree(root.right); return root;}
root
—
root.left
—
root.right
—
frames
0
swaps
0

Why it works

  1. A mirror swaps left and right at every level, not just at the root. Swapping the root's children moves two whole subtrees across; each of them still has to be mirrored inside, which is the same problem, one level smaller.
  2. No copy needed. Building a mirrored copy node by node also works but allocates n new nodes. Swapping pointers in place touches each node once: O(n) time, nothing extra but the call stack.
  3. The call stack holds the path from the root to the node being worked on, so it grows to the tree's height h: O(log n) when balanced, O(n) for a chain where each node has one child.
  4. Swap before or after the recursive calls (pre-order or post-order): both give the same mirror, as long as each node is swapped exactly once.
  5. Pitfall, in-order: invertTree(root.left), swap, invertTree(root.right) mirrors the old left subtree twice and the old right one never, because after the swap root.right is the subtree you already did.
  6. Iterative version: a queue (BFS) or stack (DFS) of nodes; pop one, swap its children, push the non-null ones. Same O(n), and no StackOverflowError on very deep trees.