Invert Binary Tree: Swap on the Way Down

If you interview at Google, Meta, Amazon, expect some version of "Invert Binary Tree". It is rated Easy, and it falls squarely into the Tree DFS pattern — pattern-first preparation beats grinding random problems every time. Part 3 of 11 in the Tree DFS arc.

The Problem

Invert a binary tree: mirror it left-right at every node, returning the root. Famous beyond its difficulty because of the 2015 Homebrew-author anecdote, and still asked as a warm-up filter. The content: transform-in-place recursion.

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

Recognizing the Tree DFS Pattern

Depth-first search commits to one branch before trying siblings — recursion (or an explicit stack) whose call structure mirrors the tree itself. Its natural questions are about paths (root to leaf), subtree properties (computed bottom-up from children), and exhaustive exploration (islands, connected regions). The recurring design decision is what each recursive call returns versus what it accumulates in shared state.

A mirror is defined recursively — the mirror of a node has its children swapped and mirrored. Structural transformations that apply the same local operation at every node are DFS with the operation at each visit; order (pre or post) is irrelevant when the operation is self-contained.

The Approach

Swap the children, then recurse into both (or recurse first and then swap — identical result). Python's tuple assignment swaps without a temporary and reads cleanly on a whiteboard.

The iterative version replaces the call stack with a deque or list of pending nodes — a 30-second rewrite worth doing aloud since this question is often a vehicle for 'now without recursion'.

Python Solution

class TreeNode:
    def __init__(self, val: int = 0, left: "TreeNode | None" = None,
                 right: "TreeNode | None" = None):
        self.val = val
        self.left = left
        self.right = right


def invert_tree(root: TreeNode | None) -> TreeNode | None:
    """Mirror the tree in place; return its root."""
    if root is None:
        return None
    root.left, root.right = root.right, root.left
    invert_tree(root.left)
    invert_tree(root.right)
    return root

Complexity

• Time: O(n) — one swap per node
• Space: O(h) — recursion depth

Interview Tips and Follow-Ups

• Pre-order vs post-order swap both work here — being able to say why (the operation is local) is worth more than the code.
• Mutating input vs returning a new mirrored tree is a fair clarifying question — ask it; interviewers note who asks about ownership.
• Pair with Symmetric Tree: a tree is symmetric exactly when it equals its inversion — one sentence connecting two questions.

That wraps part 3 of the Tree DFS arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.