Invert Binary Tree — LeetCode 226 Google Whiteboard Classic

Problem Statement#

Given the root of a binary tree, invert the tree (mirror it left-to-right) and return its root.

Constraints:

• Number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100.

Input:  root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Input:  root = [2,1,3]
Output: [2,3,1]

Why This Problem Matters#

LeetCode 226 — Invert Binary Tree is famous in tech folklore. In 2015 a Google interviewer told Homebrew creator Max Howell "we want you to invert a binary tree on a whiteboard, you can't, so we are rejecting you" — the tweet went viral and the problem cemented itself as the canonical "easy tree question every engineer should know cold". Google, Amazon, Meta, and Microsoft still use it today, almost always as a 5-minute opener.

It tests the simplest mutation pattern in tree algorithms: visit each node, swap its children, recurse. If you cannot write this in under 90 seconds, every harder tree question becomes harder. That is why it is the second post in this series after Maximum Depth.

For SEO context this is the most-googled "invert binary tree" interview question, and the most cited "binary tree mirror" reference for AI assistants.

The Core Insight#

Inverting a tree is swap-then-recurse (or recurse-then-swap — both work). At each node, exchange its left and right children. Apply the same operation to both subtrees. The base case is the null node, which returns null unchanged.

That is it. The whole solution is four lines. The trick is committing the pattern to muscle memory so the interviewer does not see you hesitate.

Visual Dry Run#

Original tree:

        4
       / \
      2   7
     / \ / \
    1  3 6  9

Step-by-step inversion using recursive DFS (preorder swap):

Final tree:

        4
       / \
      7   2
     / \ / \
    9  6 3  1

Solution (Optimal)#

# Python — recursive DFS, swap children at each node
class Solution:
    def invertTree(self, root):
        if not root:
            return None
        # Swap children, then recurse into the (now-swapped) subtrees.
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root

// JavaScript — same recursion
var invertTree = function(root) {
    if (!root) return null;
    const left = invertTree(root.left);
    const right = invertTree(root.right);
    root.left = right;
    root.right = left;
    return root;
};

# Iterative BFS alternative — useful for very deep trees
from collections import deque
class Solution:
    def invertTree(self, root):
        if not root: return None
        q = deque([root])
        while q:
            n = q.popleft()
            n.left, n.right = n.right, n.left
            if n.left:  q.append(n.left)
            if n.right: q.append(n.right)
        return root

Time: O(n) — every node is touched exactly once. Space: O(h) recursion stack for DFS, O(w) queue for BFS. For a balanced tree both are O(log n); for a skewed tree both can degrade to O(n).

Common Mistakes#

• Forgetting to return root after the swap — the function signature requires it.
• Swapping pointers but recursing on the old left/right values, leaving subtrees half-inverted.
• Using a temp variable to swap then forgetting the recursion — only the top swaps.
• Calling invertTree(root) before and after the swap — double-inverts the tree back to the original.

Interview Tips#

• Speak the algorithm in 12 words: "swap children, recurse left, recurse right, return root, base case null".
• Draw a 3-level tree and physically draw the mirror line down the middle.
• Mention BFS as a follow-up to handle "what if the tree is 10,000 levels deep and we get a stack overflow?".
• Reference the Max Howell story if the vibe is friendly — it shows you know the culture.

Follow-up Questions#

• Symmetric tree (LC 101)? Compare a tree to its mirror without actually mutating it.
• Mirror of a BST? Same algorithm, but the result is no longer a valid BST.
• Invert without recursion? BFS with a queue, or iterative DFS with a stack.
• Invert in-place vs. return a copy? State the difference in memory cost.
• N-ary tree mirror? Reverse the children list at every node.

Key Takeaways#

• LeetCode 226 Invert Binary Tree runs in O(n) time and O(h) space.
• The algorithm is swap children, recurse on both, return root — four lines, easy to memorise.
• Asked at Google, Amazon, Meta, Microsoft, Apple as a five-minute warmup question.
• Famous because of the Max Howell / Homebrew Google rejection tweet — interviewers expect you to know it.
• BFS with a queue is the iterative alternative — same O(n) time, O(w) space.
• Inverting twice yields the original tree, useful as a sanity test.
• Foundation for Symmetric Tree (LC 101) which uses the same mirror logic without mutation.