226. Invert Binary Tree

This one is famous for the wrong reason — a viral tweet about failing to whiteboard it — but it’s a clean lesson in tree recursion. Mirror a tree and the code writes itself once you spot that every node does the same tiny job. It’s a starter problem in the binary tree patterns family, and the shape here repeats in half of them.

The problem

Given the root of a binary tree, produce its mirror image: at every node, the left and right children trade places, all the way down. Return the new root. (Full statement on LeetCode.)

A quick case: [4, 2, 7] — root 4 with children 2 (left) and 7 (right) — inverts to [4, 7, 2], so 7 is now on the left. On a deeper tree the swap cascades into every subtree, not just the top level.

Intuition: one swap, repeated everywhere

The whole trick is realizing that “invert the tree” is the same instruction applied to every node: swap my two children, then make sure each of those children is itself fully inverted. There’s no clever ordering to discover — the operation is uniform, which is exactly what recursion is good at.

So the job at a node splits into three parts: invert the left subtree, invert the right subtree, then hand the swapped pointers back up. The base case is the empty node — a null has nothing to swap, so you return it untouched. That check is also what stops the recursion from walking off the end of a leaf.

Because you touch each of the $n$ nodes exactly once, the work is $O(n)$. The recursion stack only holds one root-to-current path at a time, so its depth is the tree’s height $h$ — $O(h)$, which is $O(\log n)$ for a balanced tree and $O(n)$ for a degenerate one.

Solution

The recursive version reads like the intuition. Invert both sides first, then cross the pointers:

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;          // nothing to mirror

        TreeNode left = invertTree(root.left);   // fully inverted left subtree
        TreeNode right = invertTree(root.right); // fully inverted right subtree

        root.left = right;                       // swap the two children
        root.right = left;
        return root;
    }
}

You can also do it iteratively with a queue — a breadth-first walk that swaps each node’s children as it dequeues them. Same $O(n)$ time, but the stack overflow risk on a pathologically deep tree goes away since the depth now lives in an explicit queue:

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();

            TreeNode temp = node.left;           // swap in place
            node.left = node.right;
            node.right = temp;

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        return root;
    }
}

Both mutate the tree in place and return the original root. If the interviewer wants the source tree preserved, you’d allocate new nodes instead — worth asking before you start.

Complexity

Approach	Time	Space
Recursive	$O(n)$	$O(h)$
Iterative BFS	$O(n)$	$O(n)$

The recursion wins on space for balanced trees ($O(\log n)$ stack); the queue version trades that for immunity to deep-recursion stack overflow.

In an interview

Say the recurrence out loud before touching the board: “each node swaps its children, and I recurse on both sides — the empty node is the base case.” That single sentence is what’s being graded, and it makes the three lines of code obvious. The trap is forgetting the null check, which turns the first root.left access into a NullPointerException on an empty tree.

If they push on the recursion depth, pivot to the BFS version and name why — an explicit queue can’t blow the call stack the way recursion can on a skewed tree. The same postorder “solve both subtrees, then combine” shape drives Maximum Depth of Binary Tree, and the structural walk here is a cousin of the two-tree comparison in Same Tree. The binary tree patterns hub collects the rest.

References

• LeetCode 226 — Invert Binary Tree