Skip to main content

6. Invert Binary Tree

easyAsked at Redis

Mirror a binary tree in place; Redis screens with this to confirm clean recursion and traversal hygiene before discussing skiplist traversal.

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

Problem

Given the root of a binary tree, invert the tree (swap every node's left and right children) and return its root.

Constraints

  • 0 <= nodes <= 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 = []
Output
[]

Approaches

1. BFS swap

Level-order traversal with a queue, swapping at each node.

Time
O(n)
Space
O(n)
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:

2. Recursive swap

Swap children then recurse. Cleanest expression of the invariant.

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:

Redis-specific tips

Redis interviewers expect you to call out the O(h) recursion-stack risk on skewed trees, then segue into how the skiplist's randomized levels avoid that pathology.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →