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] — any traversal works; the point is writing it cleanly.
• -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 meaningful brute force distinct from the real solution — every node’s children must be swapped exactly once, so every correct algorithm is O(n) — and the ladder starts at the classic recursion.

The insight: the mirror of a tree is a root whose left child is the mirror of the old right subtree and vice versa. Depth-first search (DFS) — the traversal that fully explores one branch before backtracking — expresses this in three lines: recurse into both children, 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


class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        root.left, root.right = self.invertTree(root.right), self.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 purely local — a node doesn’t care whether its subtrees are already mirrored — so any visit-every-node order works. Breadth-first search (BFS), the classical 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


class Solution:
    def invertTree(self, 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 your own list and you get the same traversal without recursion-depth limits; swapping on pop is all that’s needed. This is the standard mechanical 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


class Solution:
    def invertTree(self, 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, BFS all work here because each swap is independent; don’t burn interview time choosing.

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 inevitable “now without recursion” follow-up. The deeper habit: define the result recursively (“mirror = node + mirrored subtrees, swapped”) and the code writes itself.