Skip to main content

62. Binary Tree Level Order Traversal

mediumAsked at Workday

Return the level-order (BFS) traversal of a binary tree's values, grouped by level. Workday uses this for tier-by-tier org-chart processing — same shape as emitting all VPs first, then all directors, then all managers.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025-Q4)— Workday SDE2 onsite — tree BFS.
  • Blind (2026)— Workday org-chart team — direct analogy.

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

DFS and push nodes into result[depth].

Time
O(n)
Space
O(h) recursion)
function go(n, d){ if(!n) return; if(!res[d]) res[d]=[]; res[d].push(n.val); go(n.left,d+1); go(n.right,d+1); }

Tradeoff: Works but obscures the level abstraction.

2. BFS with per-level batch

Queue. Each outer iteration processes one level entirely.

Time
O(n)
Space
O(n) for queue)
function levelOrder(root) {
  if (!root) return [];
  const result = [];
  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) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

Tradeoff: BFS with 'snapshot queue length' is the canonical pattern. Each outer pass = one tree level.

Workday-specific tips

Workday grades for the 'snapshot levelSize' pattern. Without it, you'd process subsequent levels in the same iteration. Walk through this state before coding. Note shift() is O(n) in JS — for tight perf use a real deque.

Common mistakes

  • Not snapshotting queue.length — children added mid-iteration get processed at the wrong level.
  • Returning a flat array — prompt wants level-grouped.
  • Forgetting the empty-tree case.

Follow-up questions

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

  • Binary Tree Right Side View (LC 199) — last value per level.
  • Binary Tree Zigzag Level Order (LC 103).
  • 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 snapshot length?

We're appending to the queue as we process. Without snapshotting, we'd continue dequeuing past the current level's boundary.

shift() O(n) — does it matter?

For 2000 nodes, JS shift() is fine. For 10M nodes, use a deque (e.g., an index pointer that doesn't move array elements).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →