64. Binary Tree Level Order Traversal

Q: Why capture queue.length before the inner loop?

Because we add children during the loop. Without the snapshot, n keeps growing and we'd process the next level in the current iteration.

Q: Why is queue.shift slow?

On a JS Array, shift is O(n) because it reindexes all subsequent elements. For large queues, use a real deque or use indices.

mediumAsked at Salesforce

Return the level-order (BFS) traversal of a binary tree's values. Salesforce uses this as the canonical BFS template — they use the level-tracking pattern in their org-hierarchy reports.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

Glassdoor (2026-Q1)— Salesforce uses BFS for org-hierarchy and role-chart rendering.
Blind (2025-11)— Recurring on Salesforce backend phone screens.

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. DFS with depth tracking

Recurse DFS; push to result[depth].

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

function levelOrder(root) {
  const result = [];
  function dfs(node, depth) {
    if (!node) return;
    if (depth === result.length) result.push([]);
    result[depth].push(node.val);
    dfs(node.left, depth + 1);
    dfs(node.right, depth + 1);
  }
  dfs(root, 0);
  return result;
}

Tradeoff: DFS to do BFS — works but feels indirect. Salesforce prefers iterative BFS.

2. BFS with queue and level-size tracking

Queue starts with root. Each outer iteration processes one level by looping queue.length times.

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

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

Tradeoff: True BFS. Capturing queue.length before the inner loop is the trick — it freezes the level size before children are added.

Salesforce-specific tips

Salesforce uses BFS for their org-hierarchy report (each level of the management chart is a generation). They grade on the level-size trick (capturing queue.length BEFORE the inner loop). Bonus signal: mention that queue.shift is O(n) on arrays — for production code, use a deque or index-based queue.

Common mistakes

Capturing queue.length INSIDE the loop — n grows as children are added, processing later levels in the wrong level.
Using queue.shift in a tight loop on huge inputs — O(n) per shift makes the whole thing O(n^2).
Forgetting the null root case — returns [[]] instead of [].

Follow-up questions

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

Binary Tree Zigzag Level Order Traversal (LC 103).
Binary Tree Right Side View (LC 199).
Average of Levels in Binary Tree (LC 637).

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 capture queue.length before the inner loop?

Because we add children during the loop. Without the snapshot, n keeps growing and we'd process the next level in the current iteration.

Why is queue.shift slow?

On a JS Array, shift is O(n) because it reindexes all subsequent elements. For large queues, use a real deque or use indices.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →