Skip to main content

102. Binary Tree Level Order Traversal

easyAsked at Snap

Snap's story hierarchy — user stories nested inside friend-group stories nested inside curated collections — is a tree. Level-order traversal is how that hierarchy renders top-down in the UI.

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 (left to right, level by level) as a list of lists.

Constraints

  • The number of nodes is in the range [0, 2000]
  • -1000 <= Node.val <= 1000
  • Tree may be null

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

DFS with a depth parameter; append each node's value to result[depth]. Works but recursion depth equals tree height — risky for unbalanced trees.

Time
O(n)
Space
O(n) call stack
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. Iterative BFS with level batching

Queue starts with root. Each iteration drains the entire current level (snapshot queue.length before the inner loop), collects values, and enqueues children. O(n) time and space, no recursion risk.

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:

Snap-specific tips

Snap uses this to render nested story collections. The follow-up is usually 'return levels in reverse order' (trivial: result.reverse()) or 'return the rightmost node at each level' (return only last element of each batch). Have both ready.

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 Snap interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →