Invert Binary Tree: LeetCode 226 Solution and Walkthrough

Invert Binary Tree, LeetCode problem #226, holds a unique place in coding interview lore. In 2015, Max Howell — the creator of Homebrew, the package manager used by millions of developers — tweeted that Google rejected him because he could not invert a binary tree on a whiteboard. The tweet went viral and sparked a massive debate about whether coding interviews actually measure engineering ability.

Despite the controversy, invert binary tree leetcode remains one of the most-solved Easy problems on the platform, and for good reason. It is the perfect introduction to recursive tree manipulation. The solution is short, elegant, and teaches a fundamental pattern that appears in dozens of other tree problems.

In this walkthrough, you will learn two approaches to solving LeetCode 226 — a recursive DFS solution and an iterative BFS solution — along with a visual example, edge cases, and the broader pattern this problem teaches.

The problem statement is simple: given the root of a binary tree, invert the tree and return its root. Inverting a binary tree means creating its mirror image — every left child becomes the right child and every right child becomes the left child, applied recursively to every node in the tree.

Think of it like holding the tree up to a mirror. The root stays in place, but everything to the left swaps with everything to the right. This is not just swapping the immediate children of the root — you need to swap the children at every level of the tree, all the way down to the leaves.

For example, given the tree [4, 2, 7, 1, 3, 6, 9], the inverted result is [4, 7, 2, 9, 6, 3, 1]. The root node 4 stays put, but its left subtree (rooted at 2) and right subtree (rooted at 7) swap positions entirely, and within each subtree the same swap happens recursively.

The recursive approach to invert binary tree leetcode is famously concise. The idea is straightforward: at each node, swap the left and right children, then recursively invert the left subtree and the right subtree. The base case is when you reach a null node — just return null.

Here is the approach in plain English. If the root is null, return null. Otherwise, swap root.left and root.right. Then call invertTree on root.left and root.right. Finally, return root. That is the entire algorithm — four lines of logic that solve the problem completely.

The time complexity is O(n) where n is the number of nodes, because you visit every node exactly once. The space complexity is O(h) where h is the height of the tree, due to the recursion stack. In the worst case of a completely skewed tree, h equals n, making space O(n). For a balanced tree, h is log(n).

If you prefer an iterative approach, you can use breadth-first search with a queue. The idea is the same — visit every node and swap its children — but instead of using the call stack, you process nodes level by level using an explicit queue.

Start by adding the root to the queue. While the queue is not empty, dequeue a node, swap its left and right children, and enqueue both children (if they exist). When the queue is empty, every node has been processed and the tree is fully inverted.

The time complexity remains O(n) since you still visit every node once. The space complexity is O(w) where w is the maximum width of the tree. For a complete binary tree, the last level can hold up to n/2 nodes, so space is O(n) in the worst case. The BFS approach is useful when you want to avoid deep recursion stacks or when a problem specifically requires level-order processing.

Let us walk through the example tree [4, 2, 7, 1, 3, 6, 9] step by step using the recursive approach. The root is 4 with left child 2 and right child 7. Node 2 has children 1 and 3. Node 7 has children 6 and 9.

At the root (4), swap left and right: now 7 is on the left and 2 is on the right. Recurse into node 7 (now on the left): swap its children so 9 is on the left and 6 is on the right. Recurse into node 2 (now on the right): swap its children so 3 is on the left and 1 is on the right. The leaf nodes (1, 3, 6, 9) have no children, so their recursive calls return immediately.

The final tree reads [4, 7, 2, 9, 6, 3, 1] — a perfect mirror of the original. Notice that every parent-child relationship has been flipped. The same result occurs whether you use DFS or BFS, because both visit every node and perform the same swap operation.

LeetCode 226 has a few edge cases you should handle explicitly. The first is an empty tree — if root is null, return null. This is your base case and it prevents null pointer errors when trying to access left or right children on a node that does not exist.

The second edge case is a single-node tree. If the root has no children, there is nothing to swap. Your recursive function will attempt to swap null with null and return the root unchanged, which is correct behavior without any special handling.

The third edge case is an already symmetric tree. If the tree is a perfect mirror of itself, inverting it produces the exact same tree. Your algorithm handles this correctly because it does not check whether a swap is needed — it always swaps. This blind-swap approach is simpler and equally efficient compared to checking symmetry first.

Despite being an Easy problem, LeetCode 226 teaches one of the most important patterns in tree manipulation: visiting every node and modifying the tree structure through child swaps. This exact pattern — recurse, modify, return — appears in problems like Symmetric Tree (#101), Same Tree (#100), and Merge Two Binary Trees (#617).

The flip binary tree pattern also builds your intuition for when to use preorder versus postorder traversal. For this problem, preorder (swap then recurse) and postorder (recurse then swap) both work because the swap at each node is independent. However, inorder traversal does not work correctly — you would process the left child, swap, and then process the old left child again instead of the right child.

If the Google-Homebrew meme taught the industry anything, it is that simple problems can still trip up experienced engineers under pressure. The best defense is deliberate practice. YeetCode flashcards help you drill tree patterns like node swapping and recursive traversal so that problems like Invert Binary Tree become automatic, not anxiety-inducing.