LeetCode · #226

Invert Binary Tree Solution

Given the root of a binary tree, invert it — swap every left and right child — and return the root.

Section One · Problem

Problem Statement

🏷️

Difficulty

Easy

🔗

LeetCode

Problem #226

🏗️

Pattern

Recursion — post-order swap

Given the root of a binary tree, invert the tree (mirror it) and return its root. Every left child becomes the right child and vice versa, at every level.

Example

Constraints

• 0 ≤ number of nodes ≤ 100 • -100 ≤ Node.val ≤ 100

Section Two · Approach 1

Iterative BFS — O(n)

Use a queue. For each node, swap its left and right children, then enqueue both. Level-by-level inversion.

Metric	Value
Time	O(n)
Space	O(n) — queue holds up to n/2 nodes

Section Three · Approach 2

Recursive DFS — O(n)

At each node: swap left and right, then recursively invert both subtrees. Base case: null node returns null. The recursion naturally handles every level.

💡 Mental model: Imagine mirroring a family tree — at every person, swap their left and right children. Do this top-down (or bottom-up — order doesn't matter because the swap is independent at each node).

Algorithm

Base case: If root is null, return null.
Swap: temp = root.left; root.left = root.right; root.right = temp;
Recurse: invertTree(root.left); invertTree(root.right);
Return: root.

🎯 Pattern recognition:

"Transform every node" = visit all nodes + do constant work each. This is the simplest tree recursion pattern.
It appears in LC 226, LC 101 (Symmetric Tree as a variation), and any problem that modifies tree structure.

Section Four · Trace

Visual Walkthrough

Recursive inversion — swap at each node

Section Five · Implementation

Code — Java & Python

Java — Recursive

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

        invertTree(root.left);
        invertTree(root.right);
return root;
    }
}

Python — Recursive

 class Solution:
def invertTree(self, root):
if not root: return None
root.left, root.right = root.right, root.left

        self.invertTree(root.left)
        self.invertTree(root.right)
return root

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Recursive DFS	O(n)	O(h)	Call stack = tree height. O(log n) balanced, O(n) skewed.
Iterative BFS	O(n)	O(n)	Queue up to n/2 nodes at widest level.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Empty tree	`null`	Base case → return null.
Single node	`[1]`	Swap null↔null → unchanged.
Skewed (linked list)	`1→2→3`	Swaps at each level flip left↔right. Stack depth = n.

⚠ Common Mistake: Inverting only the first level (swapping root's children but not recursing). The swap must happen at every node, not just the root.

← Back to Trees problems

LearningTree

LC 226 · Invert Binary Tree — Solution & Explanation | DSA Guide