Invert Binary Tree — Recursive Mirror Swap

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

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

Inverting a binary tree 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

Intuition

Define the inverted form of a tree rooted at node X as: 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 recursive definition is the entire algorithm. The base case is trivial: an empty subtree is its own inverse. For each node, swap its two children pointers, then recurse into both subtrees and let the recursion do the rest. An iterative BFS works too — pop a node from the queue, swap its children, enqueue them.

Explanation with Example

Use the four-node tree:

Call invert(1). Conceptually we invert the right subtree at node 3 (no children, returns itself unchanged) and we invert the left subtree at node 2 (its left child 4 has no children; node 2’s children become left=None, right=node 4). Back at node 1 we assign root.left = inverted_right = node 3 and root.right = inverted_left = node 2.

Final tree:

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

call order (post-order swap):
invert(2) -> invert(1), invert(3), swap children of 2
invert(7) -> invert(6), invert(9), swap children of 7
swap children of 4

Recursive swap order: post-order returns invert each subtree

Code

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


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

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;
}

public TreeNode invertTreeIterative(TreeNode root) {
    if (root == null) return null;
    Deque<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        TreeNode tmp = node.left;
        node.left = node.right;
        node.right = tmp;
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
    return root;
}

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

TreeNode* invertTreeIterative(TreeNode* root) {
    if (!root) return nullptr;
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front(); q.pop();
        std::swap(node->left, node->right);
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
    return root;
}

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.

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

Wrap up

Inverting a 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.