Skip to main content

11. Invert Binary Tree

easyAsked at Square

Invert (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 Alex Chen, 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

Input
root = [4,2,7,1,3,6,9]
Output
[4,7,2,9,6,3,1]

Example 2

Input
root = [2,1,3]
Output
[2,3,1]

Example 3

Input
root = []
Output
[]

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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

Drill Invert Binary Tree and other Square interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →