Invert Binary Tree

The problem

Invert a binary tree: swap every left/right child (recursively). Return the root.

     4               4
   /   \           /   \
  2     7    →    7     2
 / \   / \       / \   / \
1   3 6   9     9   6 3   1

Famous “Homebrew” interview meme. Still ship it cleanly.

Recursive

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function invertTree(root: TreeNode | null): TreeNode | null {
  if (!root) return null;
  const tmp = root.left;
  root.left = invertTree(root.right);
  root.right = invertTree(tmp);
  return root;
}

Or swap then recurse both — same effect:

function invertTreeAlt(root: TreeNode | null): TreeNode | null {
  if (!root) return null;
  [root.left, root.right] = [root.right, root.left];
  invertTreeAlt(root.left);
  invertTreeAlt(root.right);
  return root;
}

Time	O(n)
Space	O(h) stack

Iterative BFS

function invertTreeBfs(root: TreeNode | null): TreeNode | null {
  if (!root) return null;
  const q: TreeNode[] = [root];
  let head = 0;
  while (head < q.length) {
    const node = q[head++];
    [node.left, node.right] = [node.right, node.left];
    if (node.left) q.push(node.left);
    if (node.right) q.push(node.right);
  }
  return root;
}

Time	O(n)
Space	O(w) width

Edge cases

• null root
• single node
• skewed tree

Common mistakes

• Swapping after both recursive calls without saving one child (overwrites)
• Returning inverted left/right without assigning

// wrong if you lose reference
root.left = invertTree(root.right);
root.right = invertTree(root.left); // left already changed!

Interview delivery

1. Mirror definition.
2. Recurse + swap.
3. Mention iterative.
4. O(n).
5. Don’t overtalk — move to harder tree question.

Mental model

Mirroring is a pure structural transform: every node swaps children. Order of recursion doesn’t matter if you save one child before overwriting. Iterative BFS/DFS do the same swap per node.

Complexity table

Approach	Time	Space
Recursion	O(n)	O(h)
BFS queue	O(n)	O(w)
Explicit stack DFS	O(n)	O(h)

Out-loud answer

“Swap left and right at every node. Recurse both sides or iterate with a queue. Null base case. O(n) time. Watch the classic bug of overwriting left before using it for right.”

Interview delivery

1. Mirror definition in one sentence.
2. Recursive swap with saved child.
3. Iterative BFS alternative.
4. Null root.
5. Move on — this is a handshake problem.

Tiny test plan

• null → null
• single node unchanged structure
• two-level tree swaps children and grandchildren appropriately
• left-only skew becomes right-only skew

Related

• Maximum Depth of Binary Tree
• Same Tree
• Binary Tree Level Order
• Validate Binary Search Tree
• JavaScript Interview Guide

Further reading

• LeetCode 226 — Invert Binary Tree
• MDN: Destructuring assignment