136. Invert Binary Tree
🔗 LeetCode Problem: 226. Invert Binary Tree
📊 Difficulty: Easy
🏷️ Topics: Binary Trees, Recursion, DFS, BFS, Tree Transformation
Problem Statement
Given the root of a binary tree, invert the tree, and return its root.
Example 1:
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Example 2:
Input: root = [2,1,3]
Output: [2,3,1]
Example 3:
Input: root = []
Output: []
Constraints:
- The number of nodes in the tree is in the range [0, 100]
- -100 <= Node.val <= 100
🌳 Visual Understanding - Drawing the Transformation!
What Does "Invert" Mean?
"Invert" = "Mirror" = "Flip horizontally"
Every node swaps its left and right children!
Original: Inverted:
4 4
/ \ / \
2 7 → 7 2
/ \ / \ / \ / \
1 3 6 9 9 6 3 1
Think of it as looking at the tree in a mirror!
Example 1: Complete Inversion
BEFORE:
4 Level 0
/ \
2 7 Level 1
/ \ / \
1 3 6 9 Level 2
AFTER:
4 Level 0 (root stays same position)
/ \
7 2 Level 1 (2 and 7 swapped!)
/ \ / \
9 6 3 1 Level 2 (all pairs swapped!)
What happened at each node:
Node 4: swap(left=2, right=7) → left=7, right=2
Node 2: swap(left=1, right=3) → left=3, right=1
Node 7: swap(left=6, right=9) → left=9, right=6
Node 1: no children, nothing to swap
Node 3: no children, nothing to swap
Node 6: no children, nothing to swap
Node 9: no children, nothing to swap
Example 2: Simple Case
BEFORE:
2
/ \
1 3
AFTER:
2
/ \
3 1
Node 2: swap(left=1, right=3) → left=3, right=1
Edge Cases:
Case 1: Empty tree
Input: null
Output: null
Nothing to invert!
Case 2: Single node
Input: 5
Output: 5
No children to swap!
Case 3: Only left child
BEFORE: AFTER:
1 1
/ \
2 2
Swap left (2) with right (null)
Result: right becomes 2, left becomes null
Case 4: Only right child
BEFORE: AFTER:
1 1
\ /
2 2
Swap left (null) with right (2)
Result: left becomes 2, right becomes null
🧠 The AHA Moment - Recursive Insight!
The Key Question:
"How do I invert a tree?"
Recursive Breakdown:
To invert a tree:
1. Invert the LEFT subtree
2. Invert the RIGHT subtree
3. SWAP left and right
Why does this work?
4
/ \
2 7
Step 1: Invert left subtree (2)
→ Returns inverted version of subtree rooted at 2
Step 2: Invert right subtree (7)
→ Returns inverted version of subtree rooted at 7
Step 3: Swap them
→ Now 7 is on left, 2 is on right
Result:
4
/ \
7 2
Perfect! The tree at node 4 is now inverted!
Visual Example - Bottom Up:
Original Tree:
4
/ \
2 7
/ \ / \
1 3 6 9
How recursion works (bottom-up):
Level 2 (leaves):
Invert(1): No children → return 1
Invert(3): No children → return 3
Invert(6): No children → return 6
Invert(9): No children → return 9
Level 1:
Invert(2):
- Invert left (1) → get 1
- Invert right (3) → get 3
- Swap: left=3, right=1
- Return node 2 (now inverted)
Invert(7):
- Invert left (6) → get 6
- Invert right (9) → get 9
- Swap: left=9, right=6
- Return node 7 (now inverted)
Level 0:
Invert(4):
- Invert left (2) → get inverted subtree
- Invert right (7) → get inverted subtree
- Swap: left=7, right=2
- Return node 4 (fully inverted!)
Result:
4
/ \
7 2
/ \ / \
9 6 3 1
🧠 Recursive Thinking - Building the Solution
Base Case:
What's the simplest tree to invert?
→ A null tree (or empty tree)
What's the inversion of null?
→ Still null!
Base Case:
if (root == null) return null;
Also works for:
- Empty tree
- Leaf nodes (after processing their null children)
Recursive Case:
For any node:
1. Recursively invert LEFT subtree
left = invertTree(root.left)
2. Recursively invert RIGHT subtree
right = invertTree(root.right)
3. SWAP the children
root.left = right
root.right = left
4. Return the node
return root
Why return root?
Parent needs the inverted subtree!
The Complete Logic:
invertTree(node):
if node is null:
return null
// Get inverted subtrees
left = invertTree(node.left)
right = invertTree(node.right)
// Swap them
node.left = right
node.right = left
// Return inverted tree
return node
🎯 Solution 1: Recursive DFS (Post-order)
Implementation:
class Solution {
public TreeNode invertTree(TreeNode root) {
// Base Case: null tree stays null
if (root == null) {
return null;
}
// Recursive Step 1: Invert left subtree
// WHY? Need to flip all descendants before swapping
TreeNode left = invertTree(root.left);
// Recursive Step 2: Invert right subtree
// WHY? Need to flip all descendants before swapping
TreeNode right = invertTree(root.right);
// Swap the children
// WHY? This is what "inverting" means!
root.left = right;
root.right = left;
// Return the inverted tree rooted at this node
// WHY? Parent needs the inverted subtree
return root;
}
}
Alternative: Swap First (Pre-order)
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
// Swap children FIRST
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
// Then invert the subtrees
// Note: root.left now points to original right!
invertTree(root.left);
invertTree(root.right);
return root;
}
}
Ultra-Concise Version:
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
// Swap and recurse in one go!
TreeNode temp = root.left;
root.left = invertTree(root.right);
root.right = invertTree(temp);
return root;
}
}
🔍 Detailed Dry Run with Recursion Visualization
Tree:
2
/ \
1 3
Complete Recursion Flow (Post-order):
CALL STACK VISUALIZATION:
Level 0: invertTree(2)
│
├─ root = 2, not null ✓
│
├─ Invert LEFT: invertTree(1) ──────────┐
│ │
│ Level 1: invertTree(1) │
│ │ │
│ ├─ root = 1, not null ✓ │
│ │ │
│ ├─ Invert LEFT: invertTree(null) │
│ │ │ │
│ │ └─ return null │
│ │ │
│ ├─ left = null │
│ │ │
│ ├─ Invert RIGHT: invertTree(null) │
│ │ │ │
│ │ └─ return null │
│ │ │
│ ├─ right = null │
│ │ │
│ ├─ Swap: left=null, right=null │
│ │ (nothing changes) │
│ │ │
│ └─ return node 1 │
│ │
├─ left = node 1 │
│ │
├─ Invert RIGHT: invertTree(3) ─────────┐
│ │
│ Level 1: invertTree(3) │
│ │ │
│ ├─ root = 3, not null ✓ │
│ │ │
│ ├─ Invert LEFT: invertTree(null) │
│ │ │ │
│ │ └─ return null │
│ │ │
│ ├─ left = null │
│ │ │
│ ├─ Invert RIGHT: invertTree(null) │
│ │ │ │
│ │ └─ return null │
│ │ │
│ ├─ right = null │
│ │ │
│ ├─ Swap: left=null, right=null │
│ │ (nothing changes) │
│ │ │
│ └─ return node 3 │
│ │
├─ right = node 3 │
│ │
├─ NOW SWAP at root (2): │
│ Before: root.left=1, root.right=3 │
│ After: root.left=3, root.right=1 │
│ │
└─ return node 2 (now inverted!) │
FINAL TREE:
2
/ \
3 1
Step-by-Step Visual Transformation:
Step 0: Original
2
/ \
1 3
Step 1: Process node 1 (leaf)
No children to swap
1
Step 2: Process node 3 (leaf)
No children to swap
3
Step 3: Process node 2 (root)
Swap left (1) with right (3)
Before: After:
2 2
/ \ / \
1 3 3 1
DONE! ✓
🔍 Detailed Dry Run - Larger Tree
Tree:
4
/ \
2 7
/ \ / \
1 3 6 9
Recursion Order (Post-order):
Call Order (DFS goes deep first):
1. invertTree(4) starts
├─ 2. invertTree(2) starts
│ ├─ 3. invertTree(1) starts
│ │ ├─ 4. invertTree(null) → return null
│ │ ├─ 5. invertTree(null) → return null
│ │ ├─ Swap: no change
│ │ └─ return node 1
│ ├─ 6. invertTree(3) starts
│ │ ├─ 7. invertTree(null) → return null
│ │ ├─ 8. invertTree(null) → return null
│ │ ├─ Swap: no change
│ │ └─ return node 3
│ ├─ Swap node 2: left=3, right=1
│ └─ return node 2 (inverted)
│
├─ 9. invertTree(7) starts
│ ├─ 10. invertTree(6) starts
│ │ ├─ 11. invertTree(null) → return null
│ │ ├─ 12. invertTree(null) → return null
│ │ ├─ Swap: no change
│ │ └─ return node 6
│ ├─ 13. invertTree(9) starts
│ │ ├─ 14. invertTree(null) → return null
│ │ ├─ 15. invertTree(null) → return null
│ │ ├─ Swap: no change
│ │ └─ return node 9
│ ├─ Swap node 7: left=9, right=6
│ └─ return node 7 (inverted)
│
├─ Swap node 4: left=7, right=2
└─ return node 4 (fully inverted!)
Total calls: 15 (7 actual nodes + 8 null checks)
Visual Transformation Steps:
Original:
4
/ \
2 7
/ \ / \
1 3 6 9
After inverting subtree at 2:
4
/ \
2 7 ← Node 2's children swapped
/ \ / \
3 1 6 9
After inverting subtree at 7:
4
/ \
2 7 ← Node 7's children swapped
/ \ / \
3 1 9 6
After swapping at root 4:
4
/ \
7 2 ← Root's children swapped
/ \ / \
9 6 3 1
DONE! ✓
🎯 Solution 2: Iterative DFS (Using Stack)
Implementation:
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
// Swap children
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
// Push children to stack (if they exist)
if (node.left != null) {
stack.push(node.left);
}
if (node.right != null) {
stack.push(node.right);
}
}
return root;
}
}
Dry Run - Iterative:
Tree:
2
/ \
1 3
Stack Operations:
Initial: stack = [2]
Iteration 1:
Pop: 2
Swap: 2's children (left=1, right=3) → (left=3, right=1)
Push: 3 (now on left), 1 (now on right)
stack = [3, 1]
Iteration 2:
Pop: 1
Swap: 1's children (both null) → no change
Push: nothing (no children)
stack = [3]
Iteration 3:
Pop: 3
Swap: 3's children (both null) → no change
Push: nothing (no children)
stack = []
Stack empty → Done!
Result:
2
/ \
3 1
🎯 Solution 3: BFS (Level Order)
Implementation:
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
// Swap children
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
// Add children to queue (if they exist)
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return root;
}
}
Dry Run - BFS:
Tree:
4
/ \
2 7
/ \ / \
1 3 6 9
Level-by-level processing:
Level 0:
queue = [4]
Process 4: swap children (2,7) → (7,2)
Add: 7, 2
queue = [7, 2]
Level 1:
Process 7: swap children (6,9) → (9,6)
Add: 9, 6
queue = [2, 9, 6]
Process 2: swap children (1,3) → (3,1)
Add: 3, 1
queue = [9, 6, 3, 1]
Level 2:
Process 9: no children
Process 6: no children
Process 3: no children
Process 1: no children
queue = []
Done!
Result:
4
/ \
7 2
/ \ / \
9 6 3 1
📊 Comparison: Recursive vs Iterative
Recursive DFS:
✓ Cleanest code (4-5 lines!)
✓ Most intuitive
✓ Natural tree traversal
✗ Uses call stack (stack overflow for very deep trees)
Time: O(n)
Space: O(h) - recursion stack
Iterative DFS:
✓ Avoids recursion stack
✓ Same traversal as recursive
✗ Slightly more code
✗ Need to manage stack explicitly
Time: O(n)
Space: O(h) - explicit stack
BFS:
✓ Level-by-level intuition
✓ Processes tree systematically
✗ More space for wide trees
✗ Not as natural as recursion
Time: O(n)
Space: O(w) where w = max width
Which to Use?
For this problem: All work equally well!
Choose based on preference:
- Want clean code? → Recursive
- Fear stack overflow? → Iterative
- Like level-order? → BFS
My recommendation: Recursive (cleanest!)
📊 Complexity Analysis
Time Complexity: O(n)
Where n = number of nodes
Why?
- Must visit every node exactly once
- At each node: O(1) work (swap)
- Total: n × O(1) = O(n)
Can't do better than O(n):
- Must touch every node to invert it!
Example:
Tree with 7 nodes → 7 visits
Tree with 100 nodes → 100 visits
Space Complexity:
Recursive: O(h)
Where h = height of tree
Why?
- Recursion call stack depth
- Maximum depth = height
Best case (balanced): O(log n)
Example: Perfect tree with 15 nodes
Height = 4 → Stack depth = 4
Worst case (skewed): O(n)
Example:
1
/
2
/
3
Height = 3 → Stack depth = 3
Iterative DFS: O(h)
Same as recursive
- Stack holds nodes along one path
- Maximum = height of tree
BFS: O(w)
Where w = maximum width of tree
Why?
- Queue holds one level at a time
- Maximum width level
Example:
1
/ \
2 3
/ \ / \
4 5 6 7
Level 3 has 4 nodes (w = 4)
Queue holds up to 4 nodes
Worst case: w = n/2 (complete tree last level)
Space: O(n)
⚠️ Common Mistakes
Mistake 1: Forgetting to Return Root
// ❌ WRONG - Doesn't return anything!
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;
// Missing: return root;
}
// Function returns null by default in some languages!
// ✓ CORRECT - Return the root
public TreeNode invertTree(TreeNode root) {
// ... same code ...
return root; // Return the inverted tree!
}
Mistake 2: Swapping Without Saving
// ❌ WRONG - Lost reference!
root.left = root.right; // Lost original left!
root.right = root.left; // Now both point to same node!
// Result: Both children point to original right child!
// ✓ CORRECT - Use temp variable
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
Mistake 3: Not Handling Null
// ❌ WRONG - NullPointerException!
public TreeNode invertTree(TreeNode root) {
TreeNode left = invertTree(root.left); // Crash if root is null!
// ...
}
// ✓ CORRECT - Check null first
public TreeNode invertTree(TreeNode root) {
if (root == null) return null; // Handle null!
// ...
}
Mistake 4: Only Swapping at Root
// ❌ WRONG - Only swaps top level!
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
return root; // Forgot to recurse!
}
// Tree: 2 Becomes: 2
// / \ / \
// 1 3 3 1
// / \
// 4 4 ← Didn't invert!
// ✓ CORRECT - Recurse on subtrees
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left); // Recurse!
invertTree(root.right); // Recurse!
return root;
}
Mistake 5: Confusing Pre-order and Post-order
// Both work, but must be consistent!
// ✓ Pre-order (swap first):
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left); // Now points to original right!
invertTree(root.right); // Now points to original left!
// ✓ Post-order (swap last):
TreeNode left = invertTree(root.left); // Invert first
TreeNode right = invertTree(root.right); // Invert first
root.left = right; // Then swap
root.right = left;
// ❌ Mixed (swap between recurse):
TreeNode left = invertTree(root.left);
TreeNode temp = root.left; // Confusing!
root.left = root.right;
// This gets messy!
🎯 Pattern Recognition - Tree Transformation
Core Pattern: Modify Tree Structure
Template for tree transformations:
TreeNode transform(TreeNode node) {
// Base case: null
if (node == null) return null;
// Option 1: Pre-order (modify first, then recurse)
modify(node);
transform(node.left);
transform(node.right);
// Option 2: Post-order (recurse first, then modify)
TreeNode left = transform(node.left);
TreeNode right = transform(node.right);
modify(node, left, right);
return node;
}
Related Problems:
1. Symmetric Tree (Problem 132)
Check if tree is mirror of itself
- Uses inversion concept
- But doesn't modify tree
- Just compares
2. Flatten Binary Tree to Linked List
Transform tree to right-skewed list
- Tree transformation
- Modifies structure
- Uses recursion
3. Convert BST to Greater Tree
Modify node values (not structure)
- Tree transformation
- Changes values, not pointers
- Uses reverse in-order
4. Delete Node in BST
Remove node and restructure
- Tree transformation
- Complex pointer manipulation
- Multiple cases
When to Use This Pattern:
✓ Modifying tree structure
✓ Swapping children
✓ Restructuring tree
✓ Converting tree format
✓ Tree rotations
📝 Quick Revision Notes
🎯 Core Concept
Invert = Mirror = Swap left and right children at every node. Use recursion: (1) Invert left subtree, (2) Invert right subtree, (3) Swap them. Base case: null returns null. Each node returns itself after inversion (parent needs the reference). Can swap first (pre-order) or swap last (post-order) - both work!
⚡ Quick Implementation
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
public static TreeNode buildTree(Integer[] arr) {
if (arr == null || arr.length == 0 || arr[0] == null) {
return null;
}
TreeNode root = new TreeNode(arr[0]);
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int i = 1;
while (!queue.isEmpty() && i < arr.length) {
TreeNode current = queue.poll();
// Process left child
if (i < arr.length) {
if (arr[i] != null) {
current.left = new TreeNode(arr[i]);
queue.offer(current.left);
}
i++;
}
// Process right child
if (i < arr.length) {
if (arr[i] != null) {
current.right = new TreeNode(arr[i]);
queue.offer(current.right);
}
i++;
}
}
return root;
}
public static void print(TreeNode root) {
if (root == null) {
System.out.println("[]");
return;
}
List<String> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node != null) {
result.add(String.valueOf(node.val));
queue.offer(node.left);
queue.offer(node.right);
} else {
result.add("null");
}
}
while (!result.isEmpty() && result.get(result.size() - 1).equals("null")) {
result.remove(result.size() - 1);
}
System.out.println(result);
}
}
class Solution {
public TreeNode invertTree(TreeNode root) {
// return recursiveDFS(root); // using normal recursion
// return iterativeDFS(root); // using stack
return iterativeBFS(root); // using queue
}
private TreeNode iterativeBFS(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
// We got a node.
TreeNode curr = queue.poll();
// Nothing to process. Ignore.
if(curr == null) {
continue;
}
// Swap its left and right children (incremental).
TreeNode temp = curr.left;
curr.left = curr.right;
curr.right = temp;
// Now, push its children onto the stack.
queue.offer(curr.left);
queue.offer(curr.right);
}
return root;
}
private TreeNode iterativeDFS(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
// We got a node.
TreeNode curr = stack.pop();
// Nothing to process. Ignore.
if(curr == null) {
continue;
}
// Swap its left and right children (incremental).
TreeNode temp = curr.left;
curr.left = curr.right;
curr.right = temp;
// Now, push its children onto the stack.
stack.push(curr.left);
stack.push(curr.right);
}
return root;
}
private TreeNode recursiveDFS(TreeNode root) {
// base case: null/leaf node
if(root == null) {
return null;
}
// invert left and right separately.
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
// Now swap them.
root.left = right;
root.right = left;
// return the swapped one.
return root;
}
public static void main(String[] args) {
Solution s = new Solution();
TreeNode res1 = s.invertTree(TreeNode.buildTree(new Integer[] {4,2,7,1,3,6,9}));
TreeNode.print(res1); // [4,7,2,9,6,3,1]
}
}
🔑 Key Insights
Why Recursion Works:
Tree: 4
/ \
2 7
To invert tree at 4:
1. Get inverted left subtree (2)
2. Get inverted right subtree (7)
3. Swap them!
Result: 4
/ \
7 2
Each subtree handles its own inversion!
Trust the recursion! ✨
Pre-order vs Post-order:
Pre-order (swap first):
- Swap children
- Then recurse on NEW positions
- root.left now points to original right!
Post-order (swap last):
- Recurse on original positions
- Get inverted subtrees back
- Then swap them
Both work! Choose what's clearer to you.
Must Return Root:
Why return root?
Parent needs the reference!
If you don't return:
- Parent loses connection to subtree
- Tree gets disconnected
Always: return root at end!
🎪 Memory Aid
"Recurse on kids, then swap 'em!"
"Mirror means swap left and right!"
"Every node swaps, every level!"
"Don't forget to return root!" ✨
⚠️ Don't Forget
- Return root at the end (parent needs it!)
- Use temp variable for swapping (don't lose reference!)
- Check null first (before accessing children)
- Recurse on both sides (not just swap at root!)
- Both pre and post-order work (be consistent!)
- Swap means both directions (left→right AND right→left)
🔗 The Swap Pattern
// Classic swap with temp variable
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
// Why temp needed?
// Without it:
root.left = root.right; // Lost original left!
root.right = root.left; // Both point to same!
// With temp:
temp = root.left; // Save left ✓
root.left = root.right; // Use right ✓
root.right = temp; // Restore left ✓
🎉 Congratulations!
You've mastered tree transformation!
What You Learned:
✅ Tree inversion - Mirroring/flipping trees
✅ Recursion for modification - Changing structure
✅ Pre-order vs Post-order - When to modify
✅ Return value importance - Parent needs reference
✅ Swap technique - Using temp variable
✅ Multiple approaches - Recursive, DFS, BFS
Pattern Evolution:
Problem 131-132: Tree Comparison
- Read-only operations
- Return boolean
- Don't modify tree
Problem 133-135: Tree Calculation/Validation
- Read-only operations
- Return int/boolean
- Don't modify tree
Problem 136: Tree Transformation
- MODIFY tree structure ✓
- Return TreeNode
- Change pointers
New skill unlocked: Tree modification!
The Famous Interview Story:
This problem is famous because:
Max Howell (creator of Homebrew) tweeted:
"Google: 90% of our engineers use the software you wrote (Homebrew),
but you can't invert a binary tree on a whiteboard so fuck off."
Moral of the story:
- Know this problem! 😄
- It's a classic
- Very common in interviews
You're now prepared! 💪
Next Steps:
Great problems to practice transformation: - Flatten Binary Tree (harder transformation) - Convert BST to Greater Tree (value modification) - Delete Node in BST (complex restructuring)
You're building powerful tree skills! 🌳🔄✨