Invert Binary Tree

Problem

Given the root of a binary tree, produce its mirror image: at every node, the left and right children swap places. Return the root of the inverted tree (modifying the tree in place is fine).

Examples

Example 1

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

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

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

Every left/right pair is swapped, at every depth.

Example 2

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

The two leaves trade places under the root.

Example 3

Input:  root = []
Output: []

An empty tree is its own mirror.

Constraints

• The number of nodes is in [0, 100].
• -100 <= Node.val <= 100.

Think about it first

TL;DR

Swap children at every node via DFS recursion (or an iterative BFS/DFS) — O(n) time, O(h) space recursive, O(w) with a queue.

Approach 1 — Recursive DFS

There is no separate brute force here. Every node’s children must be swapped exactly once, so any correct algorithm is O(n); the natural starting point is the recursion.

Inverting [4,2,7,1,3,6,9] mirrors the tree left-to-right at every level:

flowchart TB
    subgraph After
        d4[4] --- d7[7]
        d4 --- d2[2]
        d7 --- d9[9]
        d7 --- d6[6]
        d2 --- d3[3]
        d2 --- d1[1]
    end
    subgraph Before
        a4[4] --- a2[2]
        a4 --- a7[7]
        a2 --- a1[1]
        a2 --- a3[3]
        a7 --- a6[6]
        a7 --- a9[9]
    end

The insight: the mirror of a tree is a root whose left child is the mirror of the old right subtree, and whose right child is the mirror of the old left subtree. Depth-first search (DFS), the traversal that fully explores one branch before backtracking, expresses this in three lines: recurse into both children, then swap.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional


def invertTree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    if not root:
        return None
    root.left, root.right = invertTree(root.right), invertTree(root.left)
    return root

Walkthrough on [4,2,7,1,3,6,9] (example 1): the call on 4 first inverts the right subtree 7 — which swaps its leaves to become 7 → (9, 6) — and the left subtree 2 — which becomes 2 → (3, 1) — then assigns the inverted 7 as the new left child and the inverted 2 as the new right child. Result: 4 → (7 → (9,6), 2 → (3,1)), i.e. [4,7,2,9,6,3,1].

Complexity: O(n) time — each node is visited once and does O(1) work. O(h) space for the recursion stack (O(n) on a skewed tree, O(log n) balanced).

Approach 2 — Iterative BFS with a queue

The insight: each swap is local. A node does not depend on whether its subtrees are already mirrored, so any order that visits every node works. Breadth-first search (BFS), the level-by-level traversal driven by a FIFO queue, swaps children as it discovers each node.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from collections import deque
from typing import Optional


def invertTree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    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

Walkthrough on [2,1,3] (example 2): pop 2, swap → children now (3, 1), enqueue 3 then 1; pop 3 (leaf, swap of two Nones is a no-op); pop 1 likewise. Tree is [2,3,1].

Complexity: O(n) time; O(w) space where w is the maximum level width — up to n/2 for a complete tree.

Approach 3 — Iterative DFS with an explicit stack

The insight: replace the recursion’s call stack with an explicit list and you get the same traversal without recursion-depth limits. Swapping on each pop is all that is needed. This is the standard recursion-to-stack conversion.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional


def invertTree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    stack = [root] if root else []
    while stack:
        node = stack.pop()
        node.left, node.right = node.right, node.left
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return root

Walkthrough on [4,2,7,1,3,6,9]: pop 4, swap → (7, 2), push both; pop 2, swap → (3, 1), push both; pop leaves 1, 3; pop 7, swap → (9, 6); pop leaves 6, 9. Every node swapped once, final tree [4,7,2,9,6,3,1].

Complexity: O(n) time, O(h) stack space.

Common pitfalls

• Sequential assignment without a temp: root.left = root.right then root.right = root.left loses the original left subtree — Python’s tuple swap (or an explicit temp) is mandatory.
• Forgetting the None base case and dereferencing a null child.
• Swapping only the immediate children of the root — the mirror must be applied at every node.
• Over-thinking traversal order: pre-order, post-order, and BFS all work here because each swap is independent.

Pattern takeaway

When a tree transformation is defined node-locally (“at every node, do X”), any complete traversal solves it. Pick the one you can write fastest, and know the iterative variants for the common “now without recursion” follow-up. The underlying habit is to define the result recursively (“mirror = node with its two mirrored subtrees swapped”), which makes the code fall out directly.