LeetCode Invert Binary Tree: 4-Line Recursion

Intermediate 8 min read

What you'll learn

✓How to think recursively about whole-tree transformations
✓The four-line recursive solution and why it works
✓How to invert iteratively using BFS with a queue
✓How to handle the empty-tree base case correctly
✓How to discuss the famous Homebrew tweet in an interview

Prerequisites

•Read [Binary Trees Introduction](/blog/binary-trees-introduction) for node basics
•Read [Binary Trees Traversals](/blog/binary-trees-traversals) for DFS and BFS patterns

LeetCode 226 Invert Binary Tree is rated Easy and famously inspired the tweet that you cannot get a job at Google if you cannot whiteboard it. It is a perfect first recursive tree problem because the structure of the recursion mirrors the structure of the tree itself.

The Problem

Given the root of a binary tree, invert it by swapping every node’s left and right children, then return the root.

Example:

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

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

Brute Force

There is no true brute force here; even the naive idea is to do exactly what the optimal does. One approach beginners try is to collect all nodes into a list, then iterate and swap. It produces the same result but with extra space.

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

def invert_brute(root):
    if not root:
        return None
    nodes = []
    stack = [root]
    while stack:
        node = stack.pop()
        nodes.append(node)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    for node in nodes:
        node.left, node.right = node.right, node.left
    return root

It still runs in O(n) time but allocates an explicit list. We can do better with recursion.

Optimal Solution

The recursive solution is famously short. For each node, swap its children, then recurse into both.

def invert_tree(root):
    if not root:
        return None
    root.left, root.right = invert_tree(root.right), invert_tree(root.left)
    return root

An iterative BFS version uses a queue.

from collections import deque

def invert_tree_iterative(root):
    if not root:
        return None
    queue = deque([root])
    while queue:
        node = queue.popleft()
        node.left, node.right = node.right, node.left
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return root

Both visit every node exactly once.

Walk Through an Example

Use the four-node tree:

Call invert_tree(1). We recurse on the right child first because of how Python evaluates the right-hand side, then the left.

Actually, both subcalls evaluate before the tuple assignment, so let us trace conceptually instead. We invert the right subtree at node 3: it has no children, so it returns itself. We invert the left subtree at node 2: it recursively inverts its right (None) and its left (node 4), so node 2’s children become left=None, right=node 4. Node 2 returns itself.

Back at node 1, we assign root.left = inverted_right = node 3 and root.right = inverted_left = node 2.

Final tree:

Edge Cases

Empty tree: root is None. The base case returns None. Always handle this first.
Single node: no children to swap; we return the same node.
Skewed tree: a chain only along left or right pointers. Recursion depth equals the number of nodes; large inputs can hit Python’s recursion limit.
Duplicate values: the algorithm only swaps pointers and does not compare values, so duplicates are fine.

Complexity Analysis

Time: O(n) where n is the number of nodes. Every node is visited and swapped once.
Space recursive: O(h) for the call stack, where h is the tree height. Balanced is O(log n); worst case is O(n) for a skewed tree.
Space iterative: O(w) where w is the maximum width of the tree. Balanced is O(n / 2) at the deepest level.

How to Explain It in an Interview

State the recursive definition first: the inverted form of a tree rooted at node X is a tree with the same value at the root, the inverted right subtree on the left, and the inverted left subtree on the right. That sentence alone is the entire algorithm.

Then articulate the base case: an empty subtree is its own inverse. With those two pieces, the recursive code writes itself.

If asked about iteration, mention BFS with a queue (or DFS with a stack); the only difference is the traversal order, and the swap happens when each node is popped. Either works because the swap is local to each node.

Finally, address the trivia: the question is famous, but interviewers care more about the explanation than the four lines. They want to hear you describe the invariant and handle edge cases without prompting.

LeetCode 100 Same Tree, another fundamental recursive tree problem.
LeetCode 101 Symmetric Tree, which is essentially “is this tree its own inversion”.
LeetCode 104 Maximum Depth of Binary Tree for more DFS practice.
LeetCode 617 Merge Two Binary Trees for combined recursive transformation.

Wrap up

Invert Binary Tree is a great gateway to recursive thinking. The trick is to define the operation in terms of itself and trust the recursion. Once you are comfortable, move on to Symmetric Tree, which uses two pointers that recurse in mirror, and revisit Binary Trees Traversals to solidify DFS versus BFS choices.