We need to mirror a binary tree around its vertical axis. Every node's left child becomes its right child, and vice versa. This swap has to happen at every single node, not just the root.

A common mistake is thinking you only need to swap the root's children. But inversion is recursive by nature. When you swap the left and right subtrees of the root, the subtrees themselves also need to be inverted internally. The node that was in the bottom-left corner of the original tree should end up in the bottom-right corner of the inverted tree.

The key observation is that the structure of the problem is naturally recursive. To invert a tree rooted at some node, you invert the left subtree, invert the right subtree, then swap the two. This maps directly to a simple recursive algorithm.

Key Constraints:

Intuition

The most natural way to think about this problem is recursively. To invert a tree rooted at some node, we need to do three things: invert the left subtree, invert the right subtree, and then swap the left and right children of the current node.

The base case is simple. If the node is null, there's nothing to invert, so we return null.

This maps directly to a post-order DFS traversal. We go deep into the left subtree first, invert everything there, then go deep into the right subtree and invert everything there, and finally swap the two children at the current node. The beauty of recursion is that by the time we do the swap at any node, both subtrees are already fully inverted.

Actually, the order of operations is flexible here. You can swap first and then recurse (pre-order), or recurse first and then swap (post-order). Both work because swapping at a node is independent of whether the subtrees have been inverted yet. The only thing that matters is that every node gets visited and its children get swapped.

Algorithm

Example Walkthrough

Code

The recursive approach is clean and optimal in time, but it uses the implicit call stack. Can we achieve the same result iteratively using BFS?

Intuition

Instead of using recursion, we can use an explicit queue and process the tree level by level. The idea is simple: use BFS to visit every node, and at each node, swap its left and right children.

This works because the inversion at any node is independent of the order in which we visit nodes. Whether we visit top-down, bottom-up, left-to-right, or level-by-level, as long as we swap the children at every node, the tree gets fully inverted. BFS just happens to be a clean, iterative way to guarantee we visit every node.

Algorithm

Example Walkthrough

Code

The BFS approach avoids recursion but can use O(n) space for wide trees. Can we get iterative DFS with O(h) space instead?

Intuition

This approach combines the best of both worlds: iterative (no risk of call stack overflow) and DFS-style space usage of O(h). Instead of a queue (BFS), we use a stack (DFS). The logic at each node is identical: swap the children.

The stack gives us depth-first traversal order. We push a node, pop it, swap its children, then push the non-null children onto the stack. The last-in-first-out nature of the stack means we go deep before going wide, which keeps the stack size bounded by the tree height rather than the tree width.

Algorithm

Example Walkthrough

Code