226. Invert Binary Tree

226

EasyTrees and Binary Search TreesRecursive tree traversal (DFS)Swap children recursively

Invert Binary Tree

Given the root of a binary tree, invert the tree (mirror it left-to-right) and return its root. Every node's left and right subtrees are swapped.

Open official problem prompt ↗

In plain English

Produce the mirror image of a binary tree so that a left-to-right reflection of the original is returned.

Picture it like this

Hold the tree up to a mirror: every branch that pointed left now points right and vice versa, all the way down.

Example

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Why: Each node keeps its value but its two subtrees swap places, mirroring the whole tree.

Constraints

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

Pattern lesson

See the pattern, then code

Swap children recursively

↗

Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. Inverting the whole tree is the same as swapping the two children of every node; if you invert both subtrees first and then swap them, the whole tree is inverted.

New words, made simpleKnow these before the algorithm

Binary tree: A tree where each node has at most two children, called left and right.
Subtree: A node together with all of its descendants.
Height (h): The number of nodes on the longest root-to-leaf path; bounds recursion depth.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Rebuild a new tree

Correct but wastefully allocates a whole second tree when in-place swapping suffices.

Create brand-new nodes with children swapped instead of mutating in place.

Time O(n)Space O(n)

Best choiceRecursive in-place swap

Minimal code, touches each node once, uses only the call stack.

Invert both subtrees, then swap the node's two child pointers.

Time O(n)Space O(h)

The rule we keep true

Invariant

After invertTree returns for a node, the subtree rooted there is fully mirrored.

Why this is correct

Reasoning

By induction: the base case (empty node) is trivially inverted. Assuming both child subtrees are correctly inverted, swapping them makes the current subtree inverted, so the property holds at the root.

The algorithm in three movesSay these aloud before coding

1Return None for an empty node

invert(4): swap subtrees of 2 and 7

2Recursively invert the left subtree and the right subtree

node 2 -> left/right become 3,1

3Swap the node's left and right pointers

node 7 -> left/right become 9,6

4Return the current node

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readnode 4

2 · AskInvert children?

3 · Update staterecurse into 7 then 2

4 · Resultchildren of 4 will be swapped after subcalls

Key takeaway

The root's children 2 and 7 swap, and the same swap recurses into every subtree.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-4Base case
An empty node is already its own mirror, so return None to stop the recursion.
2
Lines 5Recurse then swap
Invert each subtree and assign them to the opposite side in a single tuple assignment, which evaluates the right-hand side before binding.
3
Lines 6Return node
Hand back the (now inverted) subtree root so the parent can wire it in.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Empty tree (root is None) returns None
Single node returns itself unchanged
Skewed tree where one child is always None still swaps correctly

Common beginner mistakes

Assigning root.left before capturing the old value, which loses one subtree; the tuple assignment avoids this
Forgetting the None base case and dereferencing a missing node

Check your understanding

Does the order of the two recursive calls matter for correctness?

Invert Binary Tree

Invert Binary Tree

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Trees and Binary Search Trees