Invert Binary Tree
The Prompt
Given the `root` of a binary tree, invert the tree, and return its root.
Understanding the Problem
Inverting a binary tree means producing its mirror image: at every node, the left child becomes the right child and vice versa. The picture flips horizontally, but no values change — only the left/right pointers.
The key observation is that a mirrored tree is defined recursively: the mirror of a node is the node itself with swapped children, where each child has itself been mirrored. That one sentence is the whole algorithm.
The Interview Flow
Interviewer
How would you invert a binary tree?
Candidate
This can be solved recursively. The idea is to swap the left and right children for every node in the tree.
Interviewer
Can you describe the recursive process?
Candidate
The base case for the recursion is a null node, in which case I just return null. For any non-null node, I first recursively invert its left subtree and its right subtree. After the recursive calls return, the subtrees are inverted. The final step for the current node is to swap its left and right child pointers. Then I return the node.
Interviewer
Does the order of operations matter? Swapping first vs. recursing first?
Candidate
It doesn't matter. I could swap the pointers `root.left` and `root.right` first, and then make the recursive calls on the new `root.left` and `root.right` (which were the original right and left children). The result is the same.
Interviewer
That's correct. How would you do it iteratively?
Candidate
Iteratively, I could use a queue for a Breadth-First Search (BFS) or a stack for a Depth-First Search (DFS). With a queue, I would add the root, then loop while the queue is not empty. In each step, I dequeue a node, swap its children, and then enqueue its non-null children. This process continues until all nodes are visited.
Interviewer
Both are valid. The recursive solution is often more concise. Please implement that.
Why does one swap per node finish the job?
The invariant is local: once a node has swapped its (already-inverted) children, its whole subtree is a perfect mirror. A null node is trivially its own mirror — that is the base case. Since every node performs exactly one swap and the recursion visits each node once, correctness composes bottom-up (or top-down; the order of swap vs. recurse does not matter).
Time is O(n) — one visit per node — and space is O(h) for the recursion stack, where h is the tree height: O(log n) balanced, O(n) worst case for a skewed tree.
Recursive DFS Solution
- Define a function `invertTree` that takes a tree `root` node.
- Handle the base case: if `root` is `null`, return `null`.
- Swap the left and right children of the current `root` node. A temporary variable is needed to hold one of the children during the swap.
- Recursively call `invertTree` on the new left child (which was the original right child).
- Recursively call `invertTree` on the new right child (which was the original left child).
- Return the `root` node.
Try it yourself
Write your solution and run it against 3 test cases.
Trees are given as TreeNodes; test inputs/outputs display in level order.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function invertTree(root) {
if (root === null) {
return null;
}
// Swap the children
const temp = root.left;
root.left = root.right;
root.right = temp;
// Recurse on the children
invertTree(root.left);
invertTree(root.right);
return root;
}Explanation
Invert the tree rooted at 4 with children 2 and 7 — watch the mirror form as swaps propagate.
1The original tree. We will swap left and right children at every node, starting from the root.
2Swap at the root: 7 moves to the left, 2 to the right. The subtrees under 7 and 2 still have their original orientation — recursion handles them next.
3Recursion swaps inside each subtree too: 7 now holds 9 then 6, and 2 holds 3 then 1. Every node swapped exactly once — the tree is fully mirrored.
Complexity Analysis
TIME
O(n)
SPACE
O(h)
Finished working through this one?
Mark it complete to track it on your Data Structures path.