Skip to main content

91. Invert Binary Tree

easyAsked at Ola

Mirror a binary tree by swapping left and right at every node.

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

Problem

Given the root of a binary tree, invert the tree and return its root.

Constraints

  • Number of nodes is in [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 = []
Output
[]

Approaches

1. BFS swap

Walk level by level; swap children at each visit.

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

2. Recursive swap

Swap children and recurse on both.

Time
O(n)
Space
O(h)
function invertTree(root) {
  if (!root) return null;
  [root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
  return root;
}

Tradeoff:

Ola-specific tips

Ola asks invert-tree as a fluency check; tie it to inverting a zone-tree layout for a left-hand-traffic country deployment.

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 Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →