[Easy] 226. Invert Binary Tree

Given the root of a binary tree, invert the tree, and return its root.

Thinking Process

1. Post-order Traversal: Process children before parent (or swap then recurse)

• Trees have no cycles — recursion is natural.
• Combine results from left and right subtrees at each node.
• Base case is usually null; height drives stack space.

Common Approaches

Typical techniques for this pattern:

Approach	Time	Space	Notes
Recursive DFS (this problem)	O(n)	O(h) stack	Natural for trees and graphs
Iterative DFS (stack)	O(n)	O(n)	Avoid recursion depth limits
DFS with memoization	O(n)	O(n)	Overlapping subproblems on graphs
Backtracking DFS	O(2^n) typical	O(n)	Enumerate choices with pruning

Examples

Example 1:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Before inversion:
      4
     / \
    2   7
   / \ / \
  1  3 6  9

After inversion:
      4
     / \
    7   2
   / \ / \
  9  6 3  1

Example 2:

Input: root = [2,1,3]
Output: [2,3,1]

Before inversion:
    2
   / \
  1   3

After inversion:
    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

Common Mistakes

1. Empty tree: root = null → return null
2. Single node: root = [1] → return [1] (no change)
3. Skewed tree: [1,2,null] → becomes [1,null,2]
4. Balanced tree: Works correctly for any balanced tree

5. Large tree: Handles up to 100 nodes efficiently

6. Not handling null: Forgetting to check for empty node

   // WRONG:
   TreeNode* tmp = root->left; // ❌ Crashes if root is null
   

7. Wrong traversal order: Processing parent before children (pre-order)
8. Creating new nodes: Unnecessarily creating new tree instead of modifying in-place
9. Not returning root: Forgetting to return the modified root
10. Swapping before recursion: Should swap after or during recursion

Related Problems

• LC 226: Invert Binary Tree - This problem
• LC 100: Same Tree - Check if two trees are identical
• LC 101: Symmetric Tree - Check if tree is symmetric
• LC 104: Maximum Depth of Binary Tree - Find maximum depth
• LC 111: Minimum Depth of Binary Tree - Find minimum depth
• LC 617: Merge Two Binary Trees - Merge two trees

Key Takeaways

1. Post-order Traversal: Process children before parent (or swap then recurse)
2. In-Place Modification: Modify tree structure directly, no need for new tree
3. Symmetric Operation: Swapping is symmetric - order doesn’t matter
4. Base Case: Empty node requires no action
5. Return Root: Always return the root node after modification

References

• LC 226: Invert Binary Tree on LeetCode
• LeetCode Discuss — LC 226: Invert Binary Tree
• LeetCode Editorial (may require premium)

Template Reference

• Trees