Invert Binary Tree
Mirror a tree by swapping every node's children, and see why the order of the swap matters
Problem Statement
Given the root of a binary tree, invert it — turn it into its mirror image — and return the root.
Input: root = [4, 2, 7, 1, 3, 6, 9]
Output: [4, 7, 2, 9, 6, 3, 1]
4 4
/ \ / \
2 7 → 7 2
/ \ / \ / \ / \
1 3 6 9 9 6 3 1Intuition
The word "invert" sounds like it needs a plan. It does not. Look at one node in isolation:
2 becomes 2
/ \ / \
1 3 3 1Its two children swapped places. That is the entire operation.
The key insight
Inverting a whole tree is nothing more than swapping the two children of every single node. There is no order to work out and no bookkeeping.
Do it once per node, and the mirroring happens on its own.
Why does that produce a full mirror rather than just a shuffled top? Because when you swap node 2's children, the entire subtree under 1 moves with it. Swapping a pointer moves everything hanging off it. Do that at every level and every layer flips.
The real-world version
Hold a mobile — the hanging kind above a cot — and rotate each crossbar 180°. You do not track where any individual toy ends up. You flip each bar, and every toy below it comes along.
Approach
Stop at empty
If the node is null, return null. Nothing to swap.
Swap this node's two children
A single assignment. In Python one line does it; in TypeScript use a temporary variable or destructuring.
Recurse into both children
Each child then swaps its own children, and so on down.
Return the node
Returning the root lets the caller chain the result, and lets each recursive call reattach cleanly.
Swap first or recurse first? Both work.
This is unusual. Most tree problems care deeply about ordering, but here pre-order (swap, then recurse) and post-order (recurse, then swap) both give the same answer.
The reason: swapping a node's children and inverting its subtrees are independent operations. Neither depends on the other having happened.
Compare that with Validate BST, where order is everything.
Watch it run
Solution
class TreeNode:
def __init__(self, val: int = 0, left: "TreeNode | None" = None,
right: "TreeNode | None" = None):
self.val = val
self.left = left
self.right = right
def invert_tree(root: TreeNode | None) -> TreeNode | None:
"""Mirror the tree by swapping every node's two children."""
if root is None:
return None
# Python evaluates the right side fully before assigning, so no temp needed.
root.left, root.right = root.right, root.left
invert_tree(root.left)
invert_tree(root.right)
return root
def invert_tree_iterative(root: TreeNode | None) -> TreeNode | None:
"""Same work, with an explicit stack instead of recursion."""
if root is None:
return None
stack = [root]
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 rootThe classic swap bug
Writing this without a temporary is wrong:
node.left = node.right ← node.left is now lost
node.right = node.left ← this copies the value we just overwroteBoth children end up as the original right child, and the original left subtree is unreachable — leaked, with no error.
Python's a, b = b, a and JavaScript's [a, b] = [b, a] both build the right-hand side first, which is why they are safe.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(h)
- Time — each node is visited once and does one constant-time swap.
- Space — the call stack holds one frame per level of the current path, so
O(h). Balanced trees giveO(log n); a single chain givesO(n).
Edge Cases
Related Problems
- Maximum Depth of Binary Tree — the same skeleton, returning a value instead of mutating
- Validate Binary Search Tree — where traversal order does matter
- Trees — the traversal orders explained side by side