Skip to main content

23. Binary Tree Level Order Traversal

mediumAsked at Box

Return all nodes level by level in a binary tree — Box applies BFS traversal to render nested folder hierarchies in their web UI, surfacing each depth layer of a directory tree in order.

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

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) as an array of arrays.

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

Run DFS and pass the current depth; push each node's value into result[depth], growing the result array as needed.

Time
O(n)
Space
O(n)
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:

2. Optimal — BFS queue with level snapshot

Use a queue; at the start of each iteration, snapshot the current queue length to process exactly one level at a time, then push children for the next level.

Time
O(n)
Space
O(n)
function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];
  while (queue.length) {
    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:

Box-specific tips

Box favors the BFS queue approach because it maps cleanly onto how their folder-tree API response is built: each level in the result corresponds to one pagination depth of nested folders. Interviewers will often follow up by asking you to return the traversal in reverse level order (bottom-up) — just push levels to the front of the result array or reverse at the end.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →