Invert Binary Tree: A Step-by-Step Interview Walkthrough
- 6 hours ago
- 9 min read
The Invert Binary Tree problem is famously one of the simplest problems in the interview rotation, and interviewers like it for exactly that reason. When a problem is short, there's nowhere to hide. Can you state the base case correctly? Can you write clean recursive code without overthinking it? Can you talk through your reasoning without rambling? The candidate who fumbles the base case or writes five lines of unnecessary null-checks signals that they panic on easy problems. The candidate who handles it calmly in two minutes signals composure, which earns trust for the harder problems that follow. This is a warm-up, but warm-ups still matter.
Mirroring a tree structure shows up in computer graphics (reflecting a scene graph across an axis), database query plan transformations (some optimizers mirror left-deep and right-deep join trees to explore execution alternatives), AST manipulation in compilers, and any system that stores hierarchical data where left/right or before/after orientation needs to be flipped — like rendering right-to-left language layouts from left-to-right tree structures.
Problem Statement
Given the root of a binary tree, invert the tree and return its root.
Inverting a binary tree means swapping the left and right children of every node in the tree.
Example:
4 4
/ \ / \
2 7 → 7 2
/ \ / \ / \ / \
1 3 6 9 9 6 3 11. Clarify Requirements Before Jumping Into Code
Before writing a single line, we should restate the problem in our own words and ask the kinds of questions that would change our approach.
Input: the root of a binary tree (may be null).
Output: the root of the same tree, with left and right children swapped at every node.
Details to clarify:
Can the tree be empty? Yes — we should return null in that case.
Can the tree be unbalanced or skewed? Yes — no shape guarantees.
Are we allowed to modify the tree in place? Almost always yes for this problem, but worth asking.
Should we return the same root node, or build and return a new tree? In-place is the standard expectation.
The thing to flag is that the operation is uniform — every single node undergoes the exact same transformation (swap its two children). That uniformity is a strong signal that the algorithm will be a single rule applied recursively, not a complex set of cases.
2. Identify the Category of the Question
A few signals jump out:
The input is a tree.
The operation is local — each node only needs to look at its own two children.
The operation needs to happen at every node.
The subtrees are themselves trees, so the same operation applies recursively.
That combination — tree input, local operation, self-similar subproblems — points immediately to tree recursion. This is the simplest pattern in the tree-problem family: a function that does some work at the current node, calls itself on each child, and returns. Same family as Maximum Depth, Same Tree, and Symmetric Tree.
3. Brute Force Solution
There isn't really a meaningful "brute force" for this problem in the usual sense — no exponential search to collapse, no redundant work to memoize. The most naive approach is already the optimal one: visit every node, swap its children, done.
That observation alone is useful, though. It tells us:
We have to touch every node at least once (we can't skip any, because every node needs its children swapped).
We can't touch any node more than once efficiently (no benefit to revisiting).
So the time complexity is going to be O(n) where n is the number of nodes, regardless of the approach we pick.
The interesting question isn't how fast — it's how to walk through the tree cleanly. That's a question about traversal strategy, not algorithmic complexity.
4. Brainstorm More Solutions
Step 1: How would we invert a small tree by hand?
Let's walk through inverting this tree:
4
/ \
2 7Three nodes. The job is to swap children at every node. At node 4, swap its children: 2 and 7 trade places. Now the tree looks like:
4
/ \
7 2Nodes 2 and 7 are leaves — they have no children to swap. So we're done.
Now a slightly bigger example:
4
/ \
2 7
/ \ / \
1 3 6 9If I just swap 4's children, I get this:
4
/ \
7 2
/ \ / \
6 9 1 3But that's not fully inverted — the subtrees haven't been flipped. The correct final result swaps 6 and 9 (so 9 is on the left), and swaps 1 and 3 (so 3 is on the left).
The takeaway: it's not enough to swap children at the root. We have to swap children at every node. That's a perfect recursive structure — inverting a tree means swapping the root's children and inverting each of its subtrees.
Step 2: Translate the manual process into a recurrence
Define invert(node) as the function that inverts the subtree rooted at node and returns the (now inverted) root.
The recurrence falls out of the manual walkthrough:
If node is null, there's nothing to invert — return null.
Otherwise: invert the left subtree, invert the right subtree, then swap them as node's children.
invert(node):
if node is null: return null
left = invert(node.left)
right = invert(node.right)
node.left = right
node.right = left
return nodeStep 3: Does the order of operations matter?
A small observation worth making: the three steps in the recursive case (invert left, invert right, swap) can happen in any order, and the result is the same.
We could swap children first, then recurse into the new left and new right.
We could recurse into the left and right, then swap.
We could swap, then recurse — same result, because the subtree references move with the swap.
Why? Because the recursive calls and the swap don't interact. The recursive calls only modify nodes inside the subtree they're given. The swap only modifies the pointers at the current node. They're independent operations.
This matters for two reasons. First, it makes the algorithm robust — small implementation choices don't break correctness. Second, it tells us this problem isn't really preorder or postorder in a meaningful sense. Both work because the order doesn't matter.
Step 4: What about iteration?
For completeness, we could also do this iteratively with a queue (BFS) or stack (DFS):
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
return root;
}This works fine and avoids the recursion stack. It also has a notable safety property: a very deep tree (say, 10,000 nodes all chained as left children) would blow up the recursive version's call stack but won't faze the iterative one. The iterative version uses heap memory for the queue instead of stack memory, and the heap is much larger.
A few notes on the iterative version worth pointing out:
The swap happens at the time the node is dequeued, not when it's enqueued. That keeps the logic in one place — every node, when it's processed, just swaps its own children and adds them to the queue.
The order children are enqueued doesn't matter for correctness. Whether we enqueue left first or right first, every node still gets swapped exactly once. BFS just changes the order in which the work happens.
A stack would work just as well as a queue — that would make this iterative DFS instead of iterative BFS. The choice between them is mostly stylistic for this problem, because the operation at each node doesn't depend on order.
In an interview, I'd still lead with the recursive version because it's cleaner and easier to explain. But I'd still mention the iterative alternative for completeness, and implement it if the interviewer suggests call stack is a concern.
Step 5: Complexity
The recursive function visits each of the n nodes exactly once and does O(1) work at each (one swap, two assignments). So total time is O(n) and total space is O(h) for the recursion stack, where h is the height of the tree. For a balanced tree, h = O(log n). For a skewed tree, h = O(n).
The iterative version is O(n) time and O(n) space in the worst case — the queue can hold up to a full level of the tree, which is up to n/2 nodes at the bottom of a balanced tree.
5. Discuss Trade-Offs Between Solutions
Approach | Time | Space | When I'd use it |
Recursive DFS | O(n) | O(h) | My default interview answer — cleanest code, easiest to explain |
Iterative BFS (queue) | O(n) | O(n) | If the tree might be deep and stack overflow is a concern |
Iterative DFS (stack) | O(n) | O(h) | Same as BFS but better space on skinny trees |
For a normal-looking interview problem, recursion wins. The iterative versions are mostly there as fallbacks for adversarial input or as discussion points about stack safety.
6. Pseudocode
invert(node):
if node is null:
return null
left = invert(node.left)
right = invert(node.right)
node.left = right
node.right = left
return nodeThat's the entire algorithm. Five lines of logic plus a base case.
7. Edge Cases
Things to verify before claiming we're done:
Empty tree (null root) → base case returns null immediately. ✓
Single-node tree → recurse into both (null) children, swap (no-op since both are null), return. ✓
Tree skewed entirely to one side (e.g., all left children) → recursion still works; after inversion, it becomes skewed to the other side. ✓
Very deep tree → may risk stack overflow with recursion. Iterative version handles it.
Tree with duplicate values → values are irrelevant to the algorithm; only structure matters.
The base case (node == null) handles every degenerate shape without needing special logic. That's the sign of a clean recursion.
8. Full Code
import java.util.LinkedList;
import java.util.Queue;
public class InvertBinaryTree {
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
// Recursive solution — O(n) time, O(h) space for the call stack.
// Cleanest and easiest to explain. Default interview answer.
public static TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
// Iterative solution using BFS
// Useful when the tree might be deep and a recursive
// call stack could overflow.
public static TreeNode invertTreeIterative(TreeNode root) {
if (root == null) {
return null;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
// Swap this node's children
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
// Enqueue children to process them later
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
return root;
}
}9. Test the Code
// Standard tree
TreeNode root = new TreeNode(4);
root.left = new TreeNode(2);
root.right = new TreeNode(7);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(3);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(9);
invertTree(root);
// Expected after inversion:
// 4
// / \
// 7 2
// / \ / \
// 9 6 3 1
// Empty tree
System.out.println(invertTree(null)); // null
// Single node
TreeNode single = new TreeNode(1);
invertTree(single);
// Still just the node 1, unchanged structurally
// Skewed left-only chain
TreeNode skewed = new TreeNode(1);
skewed.left = new TreeNode(2);
skewed.left.left = new TreeNode(3);
invertTree(skewed);
// Expected: 1 → right → 2 → right → 3 (now skewed to the right)
These hit the meaningful cases: a balanced tree, the null case, a single node, and a skewed chain.
10. Key Lessons
When a problem asks you to apply the same operation to every node of a tree, the algorithm is almost always a simple recursion: handle the current node, recurse into the children. The whole problem reduces to defining what "handle the current node" means.
The base case in tree recursion is usually if node == null: return .... Get this right first; everything else follows.
When the recursive subproblems are independent of one another (here, inverting the left subtree doesn't affect inverting the right), the order of operations doesn't matter. That's a hint you're working with a particularly clean recursion.
Recursion is the right default for tree problems, but be ready to discuss iterative alternatives if the tree could be deep. Stack overflow is a real concern in production code, even when it's rare in interview tests.
"Trivial" interview problems can still provide important signals about a candidate. Calmly stating the base case and walking through a small example is more impressive than complicated code that obscures simple logic.
The thing that makes Invert Binary Tree click isn't difficulty. It's the discipline of recognizing that the problem is uniform (same operation everywhere) and self-similar (subtrees are smaller versions of the whole), and then trusting that recognition enough to write a five-line solution and stop. Once you can do that without second-guessing yourself, every other simple tree problem starts to feel routine.
Good Luck and Happy Coding!
Comments