Invert Binary Tree

Difficulty: Easy

Problem

Given the root of a binary tree, invert the tree (turn it into its mirror image), and return its root. Inverting means that for EVERY node in the tree, its left and right children swap places.

Example

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Explanation: Node 4's children 2 and 7 swap. Then inside those subtrees, 1↔3 swap under 2, and 6↔9 swap under 7. The whole tree becomes its mirror image.

Brute-force approach

There is no meaningful 'brute force vs optimal' split here — the recursive swap IS the natural solution. Trees skip straight to the optimal approach.

Optimal approach

Key insight: One tiny action (swap my two children) applied at EVERY node produces the full mirror image. Recursion is the machine that applies it everywhere.

Recursively swap the left and right children of every node. Do the swap at the current node, then let recursion handle both subtrees.

Steps

  1. Base case: if the node is null, return null
  2. Swap the node's left and right child pointers
  3. Recursively invert the (new) left subtree
  4. Recursively invert the (new) right subtree
  5. Return the node

Time complexity: O(n) · Space complexity: O(h) where h = height of tree