Skip to main content

102. Binary Tree Level Order Traversal

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 Sam K., Founder, InterviewChamp.AI · Last verified

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.

More IBM coding interview questions

See all IBM problems →

Companies that also ask Binary Tree Level Order Traversal