Skip to main content

6. Invert Binary Tree

easyAsked at Notion

Swap left and right children of every node in a binary tree. Notion uses this as a one-minute tree-traversal opener.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Notion loops.

  • Glassdoor (2026-Q1)— Notion uses it as a tree warmup paired with a CRDT follow-up.
  • Blind (2025-08)— Recurring opener in Notion onsite tree rounds.

Problem

Given the root of a binary tree, invert the tree, and return its root. Inverting means mirroring the tree left-to-right.

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. BFS swap-in-queue

Level-order traversal, swap children at each node.

Time
O(n)
Space
O(w)
function invertTree(root) {
  if (!root) return null;
  const q = [root];
  while (q.length) {
    const n = q.shift();
    [n.left, n.right] = [n.right, n.left];
    if (n.left) q.push(n.left);
    if (n.right) q.push(n.right);
  }
  return root;
}

Tradeoff: Correct, avoids deep recursion. Slightly more code than DFS.

2. DFS recursive swap (optimal)

Recursively invert each subtree, then swap pointers.

Time
O(n)
Space
O(h)
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: Tiny, clean, and the recursion is its own proof of correctness.

Notion-specific tips

Notion uses this as a quick filter — finish in under a minute and pivot to the real question. Mention that this 'mirror' transform on a tree is similar to certain tree-rebalancing operations they'd discuss for CRDT block trees.

Common mistakes

  • Swapping by assignment without saving one side first — overwrites a pointer before swapping.
  • Forgetting the null base case.
  • Returning a new tree instead of mutating — wastes O(n) allocation.

Follow-up questions

An interviewer at Notion may pivot to one of these next:

  • Symmetric Tree (LC 101) — checks if a tree is its own mirror.
  • Invert only nodes at even depth.
  • Do this iteratively with O(1) extra space (Morris-style).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Must I mutate the input tree?

The problem allows mutation. Returning a new tree is acceptable but wastes memory; in-place is cleaner.

Will this break BST invariants?

Yes — inverting a BST gives a 'descending' BST that violates the standard left<root<right rule. The problem doesn't require BST behavior.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →