Skip to main content

69. Binary Tree Level Order Traversal

mediumAsked at Vercel

Return the level-order (BFS) traversal of a binary tree, grouped by level. Vercel asks this for the level-tracking BFS pattern — same shape as their dependency-graph layer expansion for parallel builds.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel platform onsite; BFS expected.
  • Blind (2026-Q1)— Listed in Vercel platform engineer screen.

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]]

Approaches

1. DFS with depth tracking

DFS; at each node, push into result[depth] (extending result if needed).

Time
O(n)
Space
O(n) result + O(h) stack
function levelOrder(root) {
  const out = [];
  function dfs(node, depth) {
    if (!node) 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: Works but uses recursion stack. BFS is the natural fit.

2. BFS with level-sized batches (optimal)

Queue holds the current level. Each iteration dequeues all of it and enqueues their children — producing one batch per level.

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

Tradeoff: Clean BFS. Using two arrays (current and next) per iteration avoids the size-snapshot trick. Equivalent to a queue with a level-sentinel.

Vercel-specific tips

Vercel grades the BFS variant. Bonus signal: discussing the size-snapshot trick (record q.length, dequeue exactly that many) versus the two-array approach. Either works; two-array is slightly more readable.

Common mistakes

  • Using a single queue without a level boundary — produces a flat traversal.
  • Forgetting to handle empty root — returns [[]] instead of [].
  • Mutating q during iteration — causes off-by-one as new children are enqueued.

Follow-up questions

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

  • Zigzag Level Order (LC 103) — alternate direction.
  • Bottom-up Level Order (LC 107) — reverse the result.
  • Right Side View (LC 199) — pick the last element of each level.

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 two arrays per iteration?

Holding 'current level' and 'next level' separately makes the boundary explicit. The alternative (single queue + size snapshot) is more compact but easier to get wrong.

BFS vs DFS — which is preferred here?

BFS reads more naturally for level-order; DFS works with a depth parameter. Both are O(n). BFS is the textbook answer for any 'level by level' question.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →