TreeEasyO(n) time · O(h) space

Invert Tree

Mahabharata — The Mirror Army — Swap Every Warrior's Left and Right

दर्पण में जैसा — बायां-दायां उलट जाता। प्रत्येक नोड पर — बच्चों की अदला-बदली करो॥

*Like in a mirror — left and right are reversed. At each node — swap the children.*

The Story

Invert a binary tree (mirror it).

For tree `[4,2,7,1,3,6,9]`: result is `[4,7,2,9,6,3,1]`.

**Elegant recursive:** ```java public TreeNode invertTree(TreeNode root) { if (root == null) return null; TreeNode temp = root.left; root.left = invertTree(root.right); // Invert right, assign to left root.right = invertTree(temp); // Invert left, assign to right return root; } ```

Or even simpler: ```java public TreeNode invertTree(TreeNode root) { if (root == null) return null; // Swap children TreeNode t = root.left; root.left = root.right; root.right = t; // Recursively invert subtrees invertTree(root.left); invertTree(root.right); return root; } ```

Both work (preorder or postorder approach).

**Iterative (BFS):** ```java Queue<TreeNode> q = new LinkedList<>(); q.offer(root); while (!q.isEmpty()) { TreeNode node = q.poll(); TreeNode t = node.left; node.left = node.right; node.right = t; if (node.left != null) q.offer(node.left); if (node.right != null) q.offer(node.right); } ```

The elegance: each node only needs one local swap. The recursion handles propagation.

The Same Recursive Approach

The recursive swap is already O(n). No simpler brute force exists.

java

// Iterative BFS version:
public TreeNode invertTreeBFS(TreeNode root) {
    if (root == null) return null;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        TreeNode node = q.poll();
        TreeNode t = node.left; node.left = node.right; node.right = t;
        if (node.left != null) q.offer(node.left);
        if (node.right != null) q.offer(node.right);
    }
    return root;
}

The Swap-and-Recurse Wisdom

Base: null → null. Swap left and right. Recurse on both children. Return root.

java

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

Step-by-Step Walkthrough

Single node [1]: no children to swap. Return 1 ✅
[1,2,3]: swap → [1,3,2]. Return [[1],[3,2]] ✅

Deep Insight

**Famous tweet:** "Homebrew cannot be installed because Xcode is not installed" — Max Howell, creator of Homebrew, was unable to solve this problem during a Google interview. Google later acknowledged this was a flawed interview question.

**The key insight:** Inverting = at every node, swap left and right, then recursively invert the (now swapped) subtrees. The local swap + recursion achieves the full mirror in O(n).

**Pre-order vs post-order:** Both work for inversion. Pre-order swaps then recurses. Post-order recurses then swaps. The result is the same.

**Connection to tr-8 (Symmetric):** Checking if a tree is symmetric uses the same 'mirror' idea but compares two subtrees instead of modifying one.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n)	O(h)	h = height, O(log n) balanced, O(n) skewed
Optimal	O(n)	O(h)	Same as recursive — optimal

Pattern Recognition

✅ Invert tree = swap children + recurse
✅ Local swap sufficient; recursion handles subtrees
✅ Pre-order or post-order both work
✅ BFS iterative equally valid

**LeetCode Trigger Phrases:**
→ "invert binary tree"
→ Mirror a tree
→ Swap left and right at every node

Brihadaranyaka Upanishad (referenced in Gita tradition)

उभे सत्यानृते तीर्त्वा तथाऽनन्दं च तद्विदुः।

Transcending both truth and untruth, they know that bliss.

Connection: The inverted tree mirrors the original exactly — every left becomes right, every right becomes left. Like a reflection in still water that shows an inverted reality that is nonetheless perfect in its symmetry, the inverted tree is a valid tree that preserves all values and relationships, merely swapping orientation. The recursive algorithm creates this mirror image through the simplest possible operation: at each node, swap — and let recursion handle the rest.