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 Sam K., 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.

More Vercel coding interview questions

See all Vercel problems →

Companies that also ask Binary Tree Level Order Traversal