Skip to main content

12. Binary Tree Level Order Traversal

mediumAsked at Mercury

Return a binary tree's nodes grouped by level from top to bottom.

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

Problem

Given the root of a binary tree, return the level order traversal of its node values as a list of lists, one per level from root to leaf.

Constraints

  • Node count in [0, 2000]
  • -1000 <= Node.val <= 1000

Examples

Example 1

Input
root = [3,9,20,null,null,15,7]
Output
[[3],[9,20],[15,7]]

Example 2

Input
root = [1]
Output
[[1]]

Approaches

1. DFS with level index

Recurse with a level number and bucket values by index.

Time
O(n)
Space
O(n)
const res=[]; const dfs=(n,d)=>{ if(!n) return; if(!res[d]) res[d]=[]; res[d].push(n.val); dfs(n.left,d+1); dfs(n.right,d+1);}; dfs(root,0); return res;

Tradeoff:

2. BFS with snapshot per round

Process the queue one level at a time, snapshotting its size before each round so each iteration drains exactly one level.

Time
O(n)
Space
O(n)
function levelOrder(root) {
  if (!root) return [];
  const res = [], q = [root];
  while (q.length) {
    const size = q.length, level = [];
    for (let i = 0; i < size; i++) {
      const n = q.shift();
      level.push(n.val);
      if (n.left) q.push(n.left);
      if (n.right) q.push(n.right);
    }
    res.push(level);
  }
  return res;
}

Tradeoff:

Mercury-specific tips

Mercury asks this to evaluate multi-account aggregation — each level mirrors an org-tree tier (parent LLC → subsidiaries → individual operating accounts) shown in their dashboard's tree view.

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 Binary Tree Level Order Traversal and other Mercury interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →