Invert Binary Tree (LeetCode 226)
You are given the root of a binary tree and must turn it into its mirror image, then hand back its root.
Mirroring a tree means every single node — not just the root — has its left and right child swapped.
Worked Examples
root = [4,2,7,1,3,6,9][4,7,2,9,6,3,1]root = [2,1,3][2,3,1]root = [][]⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range
[0, 100].-100 <= Node.val <= 100
[4]
/ [2] [7]
/ / [1] [3][6] [9] [4]
/ [7] [2]
/ / [9] [6][3] [1]Swapping only the root's children produces (7, 2) but leaves subtrees un-mirrored. Post-order DFS swaps bottom-up: (1, 3) ➔ (3, 1) and (6, 9) ➔ (9, 6), then finally (2, 7) ➔ (7, 2) at root.
Core Insight
In-place pointer swapping modifies the existing tree structure with zero heap allocations.
Real-World Scenario & Production Applications
Transforming right-to-left layout trees for internationalization (RTL UI engines) and 3D graphics mirror transforms.
Step-by-Step Execution Trace Table
| Step | Call Frame | Depth | Action | Children Before | Children After (Swap) | Rationale |
|---|---|---|---|---|---|---|
| 1 | Node 4 | d=1 | ⬇️ ENTER | (2, 7) | — | Suspends; subtrees must invert before root can swap. |
| 2 | Node 2 | d=2 | ⬇️ ENTER | (1, 3) | — | Descend left subtree. |
| 3 | Node 1 | d=3 | ⬇️↑ VISIT | (None, None) | (None, None) | Leaf: swapping (None, None) is identity. |
| 4 | Node 3 | d=3 | ⬇️↑ VISIT | (None, None) | (None, None) | Leaf: identity. |
| 5 | Node 2 | d=2 | ↑ SWAP | (1, 3) | (3, 1) | Post-order combine: swap children of 2. |
| 6 | Node 7 | d=2 | ⬇️ ENTER | (6, 9) | — | Descend right subtree of root. |
| 7 | Node 6 | d=3 | ⬇️↑ VISIT | (None, None) | (None, None) | Leaf: identity. |
| 8 | Node 9 | d=3 | ⬇️↑ VISIT | (None, None) | (None, None) | Leaf: identity. |
| 9 | Node 7 | d=2 | ↑ SWAP | (6, 9) | (9, 6) | Post-order combine: swap children of 7. |
| 10 | Node 4 | d=1 | ↑ SWAP & FINISH | (2, 7) | (7, 2) | Swap fully inverted subtrees with pointer swap! |
root = [4,2,7,1,3,6,9][4,7,2,9,6,3,1]| Step | Call Frame | Depth | Action | Children Before | Children After (Swap) | Rationale |
|---|---|---|---|---|---|---|
| 1 | Node 4 | d=1 | ⬇️ ENTER | (2, 7) | — | Suspends; subtrees must invert before root can swap. |
| 2 | Node 2 | d=2 | ⬇️ ENTER | (1, 3) | — | Descend left subtree. |
| 3 | Node 1 | d=3 | ⬇️↑ VISIT | (None, None) | (None, None) | Leaf: swapping (None, None) is identity. |
| 4 | Node 3 | d=3 | ⬇️↑ VISIT | (None, None) | (None, None) | Leaf: identity. |
| 5 | Node 2 | d=2 | ↑ SWAP | (1, 3) | (3, 1) | Post-order combine: swap children of 2. |
| 6 | Node 7 | d=2 | ⬇️ ENTER | (6, 9) | — | Descend right subtree of root. |
| 7 | Node 6 | d=3 | ⬇️↑ VISIT | (None, None) | (None, None) | Leaf: identity. |
| 8 | Node 9 | d=3 | ⬇️↑ VISIT | (None, None) | (None, None) | Leaf: identity. |
| 9 | Node 7 | d=2 | ↑ SWAP | (6, 9) | (9, 6) | Post-order combine: swap children of 7. |
| 10 | Node 4 | d=1 | ↑ SWAP & FINISH | (2, 7) | (7, 2) | Swap fully inverted subtrees with pointer swap! |
| 1 | if not root: |
| 2 | return None |
| 3 | invertTree(root.left) |
| 4 | invertTree(root.right) |
| 5 | root.left, root.right = root.right, root.left |
| 6 | return root |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Inverting a binary tree (creating its mirror image) is the quintessential example of tree structural mutation. For every node in the tree, its left child pointer and right child pointer must swap identities. This swap must propagate down every level until reaching the leaves. Because tree mutations can easily overwrite child references before they are visited, understanding the call stack's order of execution is crucial to avoiding corrupted tree structures.
🏟️ The Analogy: The Photographer and the Hall of Mirrors
Imagine a family standing in a pyramid formation for a portrait. To create a perfect mirror image of the photograph, you don't dismantle the people. You simply ask each parent to swap the positions of their left child and right child. The parents swap their kids' places, and then each child who is also a parent swaps their own children's places. Once every parent has swapped their two children, the entire family tree is perfectly mirrored.
🔑 Why It Works
Notice how Python's simultaneous assignment root.left, root.right = root.right, root.left eliminates the need for temporary pointer buffers. Whether you swap pointers before recursing (pre-order) or after recursing (post-order), every node's children are flipped exactly once in time.
Overwriting unvisited subtree pointers: In languages without tuple unpacking (
root.left, root.right = root.right, root.left), writingroot.left = invert(root.right)overwritesroot.leftbefore it can be traversed, duplicating the right subtree.Inverting subtrees twice: Calling invert on the children before or after swapping must be done consistently; doing both inverts the tree back to its original shape.
Failing on empty tree base case: Forgetting
if not root: return NonecausesAttributeErroron empty inputs or leaf child visits.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Binary tree + structural mirror transformation.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: each node swaps its left and right pointers after their subtrees have been recursively inverted.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I recursively invert the left and right subtrees, then swap the left and right pointers of the current node. This inverts the tree in
O(N)time and O(H) space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: Visits every node once, swapping its left and right child pointers in O(1) operations per node.
O(H) Auxiliary
Recursion stack depth equals tree height H.
T(N) = 2T(N/2) + O(1) = O(N)
Derivation Progression
node.left, node.right = invert(right), invert(left)
Swaps left and right pointers in-place at each node.
N node visits
Every node is visited and transformed exactly once.
O(N) total time
Direct linear scan through the tree structure.
Variable Definitions
Total number of nodes in the binary tree
Tree height (log N in balanced tree, N in skewed tree)
Memory Architecture & Bounds
O(H) Call stack frames (H in [log N, N])
O(1) In-place node mutation
O(1) Root reference
Boundary Best / Worst Cases
time, space.
time, space.
time, space.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "invert a binary tree", "mirror binary tree". Mutate-in-place structural transformation: at every node in the tree, swap its left and right child pointers, then recursively invert both subtrees.
. Operates in time with call stack.
Overwriting child references before recursion: in Python, tuple unpacking node.left, node.right = self.invertTree(node.right), self.invertTree(node.left) cleanly prevents stale pointer bugs.
Invert Binary Tree (LeetCode 226)
You are given the root of a binary tree and must turn it into its mirror image, then hand back its root.
Mirroring a tree means every single node — not just the root — has its left and right child swapped.
Worked Examples
root = [4,2,7,1,3,6,9][4,7,2,9,6,3,1]root = [2,1,3][2,3,1]root = [][]⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range
[0, 100].-100 <= Node.val <= 100
[4]
/ [2] [7]
/ / [1] [3][6] [9] [4]
/ [7] [2]
/ / [9] [6][3] [1]Swapping only the root's children produces (7, 2) but leaves subtrees un-mirrored. Post-order DFS swaps bottom-up: (1, 3) ➔ (3, 1) and (6, 9) ➔ (9, 6), then finally (2, 7) ➔ (7, 2) at root.
Core Insight
In-place pointer swapping modifies the existing tree structure with zero heap allocations.
Real-World Scenario & Production Applications
Transforming right-to-left layout trees for internationalization (RTL UI engines) and 3D graphics mirror transforms.
Step-by-Step Execution Trace Table
| Step | Call Frame | Depth | Action | Children Before | Children After (Swap) | Rationale |
|---|---|---|---|---|---|---|
| 1 | Node 4 | d=1 | ⬇️ ENTER | (2, 7) | — | Suspends; subtrees must invert before root can swap. |
| 2 | Node 2 | d=2 | ⬇️ ENTER | (1, 3) | — | Descend left subtree. |
| 3 | Node 1 | d=3 | ⬇️↑ VISIT | (None, None) | (None, None) | Leaf: swapping (None, None) is identity. |
| 4 | Node 3 | d=3 | ⬇️↑ VISIT | (None, None) | (None, None) | Leaf: identity. |
| 5 | Node 2 | d=2 | ↑ SWAP | (1, 3) | (3, 1) | Post-order combine: swap children of 2. |
| 6 | Node 7 | d=2 | ⬇️ ENTER | (6, 9) | — | Descend right subtree of root. |
| 7 | Node 6 | d=3 | ⬇️↑ VISIT | (None, None) | (None, None) | Leaf: identity. |
| 8 | Node 9 | d=3 | ⬇️↑ VISIT | (None, None) | (None, None) | Leaf: identity. |
| 9 | Node 7 | d=2 | ↑ SWAP | (6, 9) | (9, 6) | Post-order combine: swap children of 7. |
| 10 | Node 4 | d=1 | ↑ SWAP & FINISH | (2, 7) | (7, 2) | Swap fully inverted subtrees with pointer swap! |
root = [4,2,7,1,3,6,9][4,7,2,9,6,3,1]| Step | Call Frame | Depth | Action | Children Before | Children After (Swap) | Rationale |
|---|---|---|---|---|---|---|
| 1 | Node 4 | d=1 | ⬇️ ENTER | (2, 7) | — | Suspends; subtrees must invert before root can swap. |
| 2 | Node 2 | d=2 | ⬇️ ENTER | (1, 3) | — | Descend left subtree. |
| 3 | Node 1 | d=3 | ⬇️↑ VISIT | (None, None) | (None, None) | Leaf: swapping (None, None) is identity. |
| 4 | Node 3 | d=3 | ⬇️↑ VISIT | (None, None) | (None, None) | Leaf: identity. |
| 5 | Node 2 | d=2 | ↑ SWAP | (1, 3) | (3, 1) | Post-order combine: swap children of 2. |
| 6 | Node 7 | d=2 | ⬇️ ENTER | (6, 9) | — | Descend right subtree of root. |
| 7 | Node 6 | d=3 | ⬇️↑ VISIT | (None, None) | (None, None) | Leaf: identity. |
| 8 | Node 9 | d=3 | ⬇️↑ VISIT | (None, None) | (None, None) | Leaf: identity. |
| 9 | Node 7 | d=2 | ↑ SWAP | (6, 9) | (9, 6) | Post-order combine: swap children of 7. |
| 10 | Node 4 | d=1 | ↑ SWAP & FINISH | (2, 7) | (7, 2) | Swap fully inverted subtrees with pointer swap! |
| 1 | if not root: |
| 2 | return None |
| 3 | invertTree(root.left) |
| 4 | invertTree(root.right) |
| 5 | root.left, root.right = root.right, root.left |
| 6 | return root |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Inverting a binary tree (creating its mirror image) is the quintessential example of tree structural mutation. For every node in the tree, its left child pointer and right child pointer must swap identities. This swap must propagate down every level until reaching the leaves. Because tree mutations can easily overwrite child references before they are visited, understanding the call stack's order of execution is crucial to avoiding corrupted tree structures.
🏟️ The Analogy: The Photographer and the Hall of Mirrors
Imagine a family standing in a pyramid formation for a portrait. To create a perfect mirror image of the photograph, you don't dismantle the people. You simply ask each parent to swap the positions of their left child and right child. The parents swap their kids' places, and then each child who is also a parent swaps their own children's places. Once every parent has swapped their two children, the entire family tree is perfectly mirrored.
🔑 Why It Works
Notice how Python's simultaneous assignment root.left, root.right = root.right, root.left eliminates the need for temporary pointer buffers. Whether you swap pointers before recursing (pre-order) or after recursing (post-order), every node's children are flipped exactly once in time.
Overwriting unvisited subtree pointers: In languages without tuple unpacking (
root.left, root.right = root.right, root.left), writingroot.left = invert(root.right)overwritesroot.leftbefore it can be traversed, duplicating the right subtree.Inverting subtrees twice: Calling invert on the children before or after swapping must be done consistently; doing both inverts the tree back to its original shape.
Failing on empty tree base case: Forgetting
if not root: return NonecausesAttributeErroron empty inputs or leaf child visits.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Binary tree + structural mirror transformation.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: each node swaps its left and right pointers after their subtrees have been recursively inverted.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I recursively invert the left and right subtrees, then swap the left and right pointers of the current node. This inverts the tree in
O(N)time and O(H) space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: Visits every node once, swapping its left and right child pointers in O(1) operations per node.
O(H) Auxiliary
Recursion stack depth equals tree height H.
T(N) = 2T(N/2) + O(1) = O(N)
Derivation Progression
node.left, node.right = invert(right), invert(left)
Swaps left and right pointers in-place at each node.
N node visits
Every node is visited and transformed exactly once.
O(N) total time
Direct linear scan through the tree structure.
Variable Definitions
Total number of nodes in the binary tree
Tree height (log N in balanced tree, N in skewed tree)
Memory Architecture & Bounds
O(H) Call stack frames (H in [log N, N])
O(1) In-place node mutation
O(1) Root reference
Boundary Best / Worst Cases
time, space.
time, space.
time, space.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "invert a binary tree", "mirror binary tree". Mutate-in-place structural transformation: at every node in the tree, swap its left and right child pointers, then recursively invert both subtrees.
. Operates in time with call stack.
Overwriting child references before recursion: in Python, tuple unpacking node.left, node.right = self.invertTree(node.right), self.invertTree(node.left) cleanly prevents stale pointer bugs.