Invert Binary Tree

EASY✓ CHIP-TIMEDLC #226 — FULL STATEMENT ↗

The drill: Mirror a binary tree — every node’s left and right children trade places, all the way down.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A binary tree arrives, and the job is to produce its mirror image — every node's left child and right child trade places, and that swap applies all the way down, not just at the root.

The values themselves never change, only their positions relative to each other; a node that was on the left of its parent ends up on the right, and whatever subtree it carries comes along with it.

An empty tree mirrors to an empty tree — there's nothing to swap, so the answer is simply nothing at all.

EX 01

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

→ [4, 7, 2, 9, 6, 3, 1]

FULL TWO LEVELS

EX 02

root = []

→ []

EMPTY TREE

EX 03

root = [1]

→ [1]

the tree can hold anywhere from zero to a few thousand nodes
node values can be negative, zero, or positive
every node's children swap, at every depth, not only near the root

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

The whole job is one small move applied everywhere. What is the move at a single node?

HINT 2 THE STRUCTURE

Swap the two children, then let recursion (or a queue) deliver the same swap to every node below.

HINT 3 ONE STEP FROM THE ANSWER

Recursive: swap, recurse left, recurse right, return root. Iterative: a queue, swapping as you visit — same work, explicit bookkeeping.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE MIRROR PASSPATTERN · RECURSIVE SWAProot = [4, 2, 7, 1, 3, 6, 9]

STEP 1

The whole job is one move — swap a node's two children — applied everywhere.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/invert-binary-tree.py — RACE PACE

LANG ▸

PACE ▸

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

TIME O(N)SPACE O(H)PYTHON · RACE PACE · 8 LN

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        queue = [root]
        while queue:
            node = queue.pop(0)
            node.left, node.right = node.right, node.left
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return root

TIME O(N)SPACE O(N)PYTHON · TRAINING PACE · 13 LN

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

TIME O(N)SPACE O(H)JAVA · RACE PACE · 13 LN

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

TIME O(N)SPACE O(N)JAVA · TRAINING PACE · 22 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED