11. Invert Binary Tree
easyAsked at SquareInvert (mirror) a binary tree by swapping every node's left and right child. Square asks this to test whether you can write clean recursive tree code — the same readability they expect in their state-machine traversal code for transaction lifecycles.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Square loops.
- Blind (2025-09)— Square Reader interview.
- LeetCode Discuss (2026)— Cash App backend phone screen.
Problem
Given the root of a binary tree, invert the tree, and return its root.
Constraints
The number of nodes in the tree is in the range [0, 100].-100 <= Node.val <= 100
Examples
Example 1
root = [4,2,7,1,3,6,9][4,7,2,9,6,3,1]Example 2
root = [2,1,3][2,3,1]Example 3
root = [][]Approaches
1. Recursive swap
Swap left and right at the current node, then recurse on both children.
- Time
- O(n)
- Space
- O(h) recursion stack
function invertTree(root) {
if (!root) return null;
const left = invertTree(root.left);
const right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}Tradeoff: O(n) time. Stack height is O(h); fine for balanced trees, risky for skewed ones.
2. Iterative BFS with queue
Use a queue. For each dequeued node, swap children and enqueue both.
- Time
- O(n)
- Space
- O(w) where w is max width
function invertTree(root) {
if (!root) return null;
const q = [root];
while (q.length) {
const node = q.shift();
[node.left, node.right] = [node.right, node.left];
if (node.left) q.push(node.left);
if (node.right) q.push(node.right);
}
return root;
}Tradeoff: Iterative — avoids stack overflow on deep skewed trees. Square interviewers like both versions.
Square-specific tips
Square interviewers grade this on whether you state the recursive contract explicitly: 'invertTree returns the root of the (now-mirrored) subtree.' Mention the stack-overflow risk on skewed inputs and offer the iterative version proactively — it's the same instinct they want in production POS code where unbounded recursion is a no-go.
Common mistakes
- Forgetting to handle null root.
- Recursing before swapping in a way that double-swaps — pick an order and stick with it.
- Using shift() on a JS array — that's O(n) per shift. Use an index pointer for true O(1) dequeue.
Follow-up questions
An interviewer at Square may pivot to one of these next:
- Verify a tree is the mirror of another (LC 101 Symmetric Tree).
- Invert iteratively with a stack (DFS) instead of a queue (BFS).
- What if the tree is huge and won't fit in memory?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why not swap children before recursing?
Either order works; just be consistent. Swap-then-recurse and recurse-then-swap both reach the same final state.
Is the iterative version always better?
It avoids recursion-depth limits but uses queue memory proportional to tree width. For balanced trees, recursion's O(log n) stack is usually fine.