Invert Binary Tree (LC 226)

Pattern: DFS — Swap Children at Every Node Difficulty: Easy Key Concept: At each node, swap its left and right children. Recurse on both. Result is the mirror image of the original tree.

Problem Statement

Given the root of a binary tree, invert the tree (every node’s left and right children are swapped) and return its root.

Example

• root = [4,2,7,1,3,6,9] → [4,7,2,9,6,3,1]

      4                       4
    /   \                   /   \
   2     7      →          7     2
  / \   / \              / \   / \
 1   3 6   9            9   6 3   1

---

1. Algorithm & Pseudocode

Recursive (Post-order or Pre-order — both work)

invert(node):
    if node == null: return null
    left  = invert(node.left)
    right = invert(node.right)
    node.left  = right
    node.right = left
    return node

Iterative — BFS

queue.offer(root)
while queue not empty:
    n = queue.poll()
    swap n.left, n.right
    if n.left  != null: queue.offer(n.left)
    if n.right != null: queue.offer(n.right)

---

2. Step-by-Step Analysis

Why it works Inverting = mirroring = swapping children at every node. The recursion structure ensures every node gets swapped exactly once.

Pre-order vs. post-order Both work. Pre-order swaps then recurses; post-order recurses then swaps. Identical final tree.

Why returning node from invert Allows assignment in one line if a parent wants to wire up; the outer caller uses the returned root.

Edge case null → return null. Single node → returns itself unchanged.

ASCII Trace

Pre-order recursion on root=4:
swap(L=2, R=7) → 4 now has left=7, right=2
  recurse left subtree (originally 7 subtree, now at node 4.left = 7):
    swap(6, 9)
      recurse on 9 → leaf, swap no-op
      recurse on 6 → leaf, swap no-op
  recurse right subtree (originally 2 subtree, now at node 4.right = 2):
    swap(1, 3)
      ...

---

3. The Dry Run

Tree: 4 → (2 → (1, 3), 7 → (6, 9))

Visit	Node	Children before	Children after
1	4	(2, 7)	(7, 2)
2	7	(6, 9)	(9, 6)
3	9	(—, —)	(—, —)
4	6	(—, —)	(—, —)
5	2	(1, 3)	(3, 1)
6	3	(—, —)	(—, —)
7	1	(—, —)	(—, —)

Result: 4 → (7 → (9, 6), 2 → (3, 1)) ✓

---

4. Java Solution

Recursive

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode left  = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left  = right;
        root.right = left;
        return root;
    }
}

Time: (O(n)) Space: (O(h)) — recursion depth

Iterative BFS

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        Queue<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode n = q.poll();
            TreeNode t = n.left; n.left = n.right; n.right = t;
            if (n.left  != null) q.offer(n.left);
            if (n.right != null) q.offer(n.right);
        }
        return root;
    }
}

Time: (O(n)) Space: (O(w)) — queue holds up to max width

---

5. The “Java vs. Others” Edge

• ArrayDeque (preferred) forbids null elements — we check before offer.
• Java has no built-in tuple swap, so use a temp variable.
• Trivia: the famous “Max Howell / Homebrew / Google interview” rejection was supposedly about this problem.

---

6. Complexity Summary

Approach	Time	Space	Notes
Recursive	O(n)	O(h)	Cleanest
BFS	O(n)	O(w)	Avoids deep recursion