Skip to main content

102. Binary Tree Level Order Traversal

mediumAsked at Apple

Binary Tree Level Order Traversal is Apple's canonical BFS-on-a-tree question. Process the queue one level at a time by snapshotting its size at the start of each iteration. Apple grades on whether you remember the size snapshot — most candidates accidentally bleed levels together.

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

Source citations

Public interview reports confirming this problem appears in Apple loops.

  • Glassdoor (2026-Q1)— Apple SWE phone-screen reports list Level Order as a recurring 20-minute BFS warm-up.
  • Blind (2025-11)— Apple new-grad and ICT3 reports cite Level Order as the canonical BFS pattern question.

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 level-size snapshot (optimal)

Standard queue BFS, but at the start of each outer iteration, snapshot the queue's current size and process exactly that many nodes — those are the current level.

Time
O(n)
Space
O(n) for queue and output
function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];
  while (queue.length) {
    const size = queue.length;
    const level = [];
    for (let i = 0; i < size; 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: Linear time, linear space. The size snapshot is the trick — you must read queue.length BEFORE the inner loop, not inside it (because the inner loop appends to the queue and would loop forever).

2. DFS with level index

Recurse with (node, depth). Push node.val to result[depth], creating result[depth] = [] when needed.

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

Tradeoff: Same complexity. DFS produces level order because we always recurse left before right and use depth as the index. Apple accepts either; BFS is preferred because the result naturally falls out level-by-level.

Apple-specific tips

Apple's grade is on the size snapshot in the BFS version. Mention it explicitly: 'I'll snapshot queue.length BEFORE the inner loop, because the inner loop appends children, and I want to stop at the end of the current level.' Without that sentence, candidates often write a runaway loop that produces a single big level.

Common mistakes

  • Reading queue.length inside the inner loop condition — bleeds levels together.
  • Using queue.shift() in a hot loop in JavaScript — O(n) per shift, but acceptable at n <= 2000 constraint.
  • Forgetting the empty-root case (return [] not [[]] ).

Follow-up questions

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

  • Binary Tree Zigzag Level Order Traversal (LC 103) — alternate direction per level.
  • Binary Tree Right Side View (LC 199) — last node of each level.
  • Average of Levels in Binary Tree (LC 637) — sum per 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

BFS or DFS?

Both work. BFS is the canonical answer because the queue naturally yields level order. DFS works by passing depth and indexing the result.

Is queue.shift() really O(n)?

In JavaScript yes — array.shift() shifts every element. For LeetCode constraints (n <= 2000) the difference is negligible; for production use a real queue.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →