Skip to main content

16. Binary Tree Level Order Traversal

mediumAsked at Activision

Return the values of a binary tree by level — Activision uses this to gauge BFS fluency before matchmaking bracket-tier traversal problems.

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

Problem

Given the root of a binary tree, return the level order traversal of its nodes' values — left to right, level by level — as a list of lists.

Constraints

  • Node count in range [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. Recursive with depth

DFS carrying depth; append each value to result[depth].

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

Tradeoff:

2. Iterative BFS with queue

Standard BFS — pop one level per outer iteration, collect values, push children. Clean and idiomatic.

Time
O(n)
Space
O(n)
function levelOrder(root) {
  if (!root) return [];
  const out = [];
  let q = [root];
  while (q.length) {
    const level = [];
    const next = [];
    for (const n of q) {
      level.push(n.val);
      if (n.left) next.push(n.left);
      if (n.right) next.push(n.right);
    }
    out.push(level);
    q = next;
  }
  return out;
}

Tradeoff:

Activision-specific tips

Activision likes when you separate per-level snapshot from the queue itself — same shape they use when broadcasting matchmaking bracket updates tier by tier.

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

Practice these live with InterviewChamp.AI →