Invert Binary Tree LeetCode 226 Deep Dive

LeetCode 226 — Invert Binary Tree — gives you the root of a binary tree and asks you to invert it, producing the mirror image. Inverting a binary tree means swapping the left and right children at every node throughout the entire tree, from root to leaves. After the inversion, each node's left subtree is what was previously its right subtree, and vice versa.

This problem is labeled Easy and is one of the most recognized problems in competitive programming lore. It can be solved recursively in fewer than 4 lines of code, yet it tests understanding of tree traversal, recursion, and the relationship between different algorithmic approaches. The iterative solutions using BFS and DFS add depth to an otherwise brief problem.

The constraints are straightforward: the tree can have between 0 and 100 nodes, and node values are integers between -100 and 100. An empty tree (null root) should simply return null — this is the natural recursive base case and requires no special handling.

In 2015, Max Howell — the creator of Homebrew, the most widely used macOS package manager — tweeted that Google had rejected him because he could not invert a binary tree on a whiteboard. The tweet went viral and ignited a fierce debate about whether whiteboard coding interviews accurately assess engineering ability. Howell's software was installed on millions of machines, yet a single algorithmic puzzle had disqualified him.

The meme has endured for over a decade. It surfaces every time someone questions the value of algorithm interviews, and the phrase "invert a binary tree" has become shorthand for the perceived disconnect between real-world engineering and interview performance. Whether you agree with the critique or not, the problem itself is genuinely useful for teaching recursive tree thinking.

The irony is that LeetCode 226 is actually an excellent teaching problem. It has a clean recursive solution, multiple valid iterative approaches, and illustrates a key insight: the order in which you process nodes does not matter when each operation is local and independent. It is the kind of problem that reveals how recursion mirrors the structure of the data it operates on.

The recursive solution is the most natural fit for this problem. A binary tree is a recursive structure — each node is the root of its own subtree — so inverting it recursively mirrors the structure perfectly. The logic is: if the current node is null, return null (base case). Otherwise, swap its left and right children, then recursively invert both subtrees.

In Python, this is literally 4 lines: def invertTree(root): if not root: return None; root.left, root.right = root.right, root.left; invertTree(root.left); invertTree(root.right); return root. The swap happens before recursing, making this a preorder traversal — but as noted, postorder (swap after recursing) also works correctly.

The time complexity is O(n) because every node is visited exactly once. The space complexity is O(h) where h is the height of the tree, due to the recursion call stack. In the worst case (a completely unbalanced tree), h equals n, giving O(n) space. For a balanced tree, h is O(log n).

The iterative BFS approach uses a queue to process nodes level by level. Start by enqueuing the root. At each step, dequeue a node, swap its left and right children, then enqueue both children (if non-null). Continue until the queue is empty. The tree is fully inverted when every node has been processed.

In Python, use collections.deque for efficient O(1) popleft operations: from collections import deque; q = deque([root]); while q: node = q.popleft(); node.left, node.right = node.right, node.left; if node.left: q.append(node.left); if node.right: q.append(node.right); return root. This processes all nodes at depth 0, then depth 1, then depth 2, and so on.

BFS is useful when you want to process the tree level by level, or when the tree is very deep and you want to avoid Python's recursion limit. The time complexity remains O(n) and the space complexity is O(w), where w is the maximum width of the tree — the maximum number of nodes at any single level.

The iterative DFS approach is structurally identical to BFS but replaces the queue with a stack. Push the root onto the stack. At each step, pop a node, swap its children, then push both non-null children onto the stack. The stack causes depth-first processing — the most recently pushed child is processed next, diving deep before backtracking.

In Python: stack = [root]; while stack: node = stack.pop(); node.left, node.right = node.right, node.left; if node.left: stack.append(node.left); if node.right: stack.append(node.right); return root. The only difference from BFS is pop() instead of popleft() and a list instead of a deque — the swap logic is identical.

Iterative DFS mimics the call stack of the recursive solution without the overhead of actual function calls. For very deep trees it avoids hitting Python's default recursion limit (usually 1000 frames), making it the safest iterative option for production use. Time complexity is O(n) and space complexity is O(h) for the stack depth.

Python recursive (4 lines): def invertTree(root): if not root: return None; root.left, root.right = root.right, root.left; invertTree(root.left); invertTree(root.right); return root. Python BFS: from collections import deque; q = deque([root]); while q: n = q.popleft(); n.left, n.right = n.right, n.left; q.extend(c for c in [n.left, n.right] if c); return root. Both run in O(n) time and O(n) space.

Java recursive: public TreeNode invertTree(TreeNode root) { if (root == null) return null; TreeNode tmp = root.left; root.left = root.right; root.right = tmp; invertTree(root.left); invertTree(root.right); return root; }. Java iterative BFS: Queue<TreeNode> q = new LinkedList<>(); q.add(root); while (!q.isEmpty()) { TreeNode n = q.poll(); TreeNode tmp = n.left; n.left = n.right; n.right = tmp; if (n.left != null) q.add(n.left); if (n.right != null) q.add(n.right); } return root;.

All three versions — recursive, BFS, DFS stack — run in O(n) time and O(n) space. The recursive version has the smallest code footprint and is preferred in interviews. The iterative versions are preferred in production systems with deep trees. Java uses a temporary variable for swapping since it lacks Python's tuple swap syntax.

Symmetric Tree (LeetCode 101) is the natural follow-up: instead of inverting a tree, you check whether it is already symmetric (a mirror of itself). The recursive structure is similar — compare left and right subtrees — but the logic checks equality rather than performing swaps. Solving both problems back to back reinforces the mirroring concept deeply.

Same Tree (LeetCode 100) and Count Good Nodes (LeetCode 1448) round out the tree fundamentals family. Same Tree checks structural and value equality recursively, using the same null base case pattern. Count Good Nodes uses preorder DFS to track path maximums downward — a step up in complexity that builds on the recursive tree pattern established by Invert Binary Tree.

Lowest Common Ancestor (LeetCode 236) is the next major tree problem after this group. It uses postorder DFS where information bubbles up from children to parents — the directional opposite of the downward-passing pattern. Together, Invert Binary Tree (local swap), Count Good Nodes (pass down), and LCA (bubble up) form a complete introduction to tree recursion patterns.