102. Binary Tree Level Order Traversal

Q: Why BFS instead of DFS?

BFS visits nodes in level order naturally — that's the whole point of the queue. DFS can produce the same output by passing a depth parameter, but BFS's queue-size snapshot is the canonical answer because it matches the problem's level-by-level structure exactly.

Q: Why is Array.shift() considered slow here?

JavaScript Array.shift() is O(n) because it must re-index every element. For an interview, mention that the queue is conceptually FIFO and that a real implementation would use a circular buffer or a doubly-ended deque. The shift-based version still passes LeetCode but isn't the production answer.

mediumAsked at IBM

Binary Tree Level Order Traversal is IBM's BFS-on-trees screener. The interviewer is grading whether you reach for an explicit queue, whether you use the queue-size snapshot trick to delimit levels, and whether you handle the empty-tree edge case cleanly.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in IBM loops.

Glassdoor (2026-Q1)— IBM SWE-2 / SWE-3 onsite recurring tree-traversal problem.
LeetCode (2026-Q1)— Top-25 IBM-tagged problem (medium tier).
GeeksforGeeks (2025-12)— Listed in IBM interview-experience archive.

Problem

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Constraints

The number of nodes in the tree is in the 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]]

Example 3

Input

root = []

Output

[]

Approaches

1. BFS with queue-size snapshot (optimal)

Use a queue. At the start of each level, snapshot the queue size; only process that many nodes for the current level.

Time: O(n)
Space: O(w) where w is max width

function levelOrder(root) {
  if (root === null) return [];
  const out = [];
  const queue = [root];
  while (queue.length > 0) {
    const levelSize = queue.length;
    const level = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left !== null) queue.push(node.left);
      if (node.right !== null) queue.push(node.right);
    }
    out.push(level);
  }
  return out;
}

Tradeoff: Canonical answer. The snapshot trick — capture `queue.length` once at the start of the level — is the line candidates often forget. Without it you can't tell where one level ends and the next begins.

2. DFS with explicit level index

Recurse depth-first, passing the current depth. Append to out[depth] (creating the sub-array if missing).

Time: O(n)
Space: O(h) call stack

function levelOrderDFS(root) {
  const out = [];
  const dfs = (node, depth) => {
    if (node === null) return;
    if (out.length === depth) out.push([]);
    out[depth].push(node.val);
    dfs(node.left, depth + 1);
    dfs(node.right, depth + 1);
  };
  dfs(root, 0);
  return out;
}

Tradeoff: Same O(n) time, O(h) stack instead of O(w) queue — wins on tall skinny trees, loses on wide shallow trees. Mention this when the interviewer asks 'what if memory is constrained and the tree is shallow but wide?'

IBM-specific tips

IBM specifically tests the queue-size snapshot pattern on tree-BFS problems. State 'I snapshot the queue size before processing the level so I know exactly how many nodes belong to this row.' That sentence is the rubric checkbox. Without it, you risk mixing children from level k into the same output row as their parents on level k. Always handle root === null as the first line.

Common mistakes

Reading queue.length inside the inner loop instead of snapshotting before — the size changes as you push children, breaking the level boundary.
Using Array.shift() on a long queue — O(n) per shift; switch to head-index for true O(1) dequeue.
Forgetting to check root === null at the top — recurses into a null and crashes.
Pushing nulls onto the queue without filtering — the null check moves from push-time to pop-time which is more error-prone.

Follow-up questions

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

Binary Tree Zigzag Level Order Traversal (LeetCode 103) — reverse every other level.
Binary Tree Right Side View (LeetCode 199) — emit only the last node per level.
Average of Levels in Binary Tree (LeetCode 637).
Cousins in Binary Tree (LeetCode 993).

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why BFS instead of DFS?

BFS visits nodes in level order naturally — that's the whole point of the queue. DFS can produce the same output by passing a depth parameter, but BFS's queue-size snapshot is the canonical answer because it matches the problem's level-by-level structure exactly.

Why is Array.shift() considered slow here?

JavaScript Array.shift() is O(n) because it must re-index every element. For an interview, mention that the queue is conceptually FIFO and that a real implementation would use a circular buffer or a doubly-ended deque. The shift-based version still passes LeetCode but isn't the production answer.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Binary Tree Level Order Traversal and other IBM interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →