Invert Binary Tree easy

Description

Given the root of a binary tree, invert it — swap every node’s left and right child throughout the tree — and return the root.

Examples

> Case 1:
    Input:        4                  Output:      4
                 / \                              / \
                2   7                            7   2
               / \ / \                          / \ / \
              1  3 6  9                        9  6 3  1
 
> Case 2:
    Input:  [2, 1, 3]
    Output: [2, 3, 1]
 
> Case 3:
    Input:  []
    Output: []

The famous “Homebrew interview”

This problem is famously the one Max Howell (author of Homebrew, a Mac package manager that powers most of Apple’s development tools) was reportedly rejected from Google for not being able to whiteboard. The internet still memes about it. Be ready.

The solution is three lines.

The recursive answer

Three-question recipe:

1. Base case: inverting an empty tree gives the empty tree.
2. Recursive case: invert the left and right subtrees, then swap them.
3. Combine: assign the swapped pointers back to the node.

TreeNode* invertTree(TreeNode* root) {
    if (root == nullptr) return nullptr;
    TreeNode* left = invertTree(root->left);
    TreeNode* right = invertTree(root->right);
    root->left = right;
    root->right = left;
    return root;
}

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

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode left  = invertTree(root.left);
    TreeNode right = invertTree(root.right);
    root.left  = right;
    root.right = left;
    return root;
}

Iterative variant (with a queue or stack)

Same idea, just iterating through nodes and swapping children:

from collections import deque
 
def invert_tree(root):
    if root is None: 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

Order of visits doesn’t matter — every node gets swapped exactly once regardless.

Why it works

Each node swaps its two child pointers. Before the swap, the subtrees are correctly inverted (by the recursive precondition). After the swap, the left child is what was the right inverted subtree, and vice versa. The result is the full inversion.

Analysis

• Time: O(n) — every node touched once.
• Space: O(h) for recursion stack; O(w) for the iterative BFS queue.