Skip to main content

74. Binary Tree Level Order Traversal

mediumAsked at Snowflake

BFS a binary tree and group nodes by level. Snowflake asks this to test queue-based BFS — directly relevant to plan-tree topological traversal during cost computation.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake compiler-team uses this to set up plan-tree DAG traversal.
  • LeetCode Discuss (2025-10)— Reported at Snowflake new-grad 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]]

Approaches

1. Recursive with depth tracking

DFS passing depth; append val to result[depth].

Time
O(n)
Space
O(n)
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: Works but DFS plus depth-bucketing — clever but less idiomatic than BFS.

2. BFS with queue (optimal)

Standard BFS: queue starts with root. Each iteration pops the whole level at once.

Time
O(n)
Space
O(width)
function levelOrder(root) {
  if (!root) return [];
  const result = [];
  let queue = [root];
  while (queue.length) {
    const level = [];
    const next = [];
    for (const n of queue) {
      level.push(n.val);
      if (n.left) next.push(n.left);
      if (n.right) next.push(n.right);
    }
    result.push(level);
    queue = next;
  }
  return result;
}

Tradeoff: Idiomatic BFS. Memory bounded by max width of the tree.

Snowflake-specific tips

Snowflake interviewers want the level-aware BFS (pop the whole level at once, not one-at-a-time). Bonus signal: connect to plan-tree topological cost computation — bottom-up cost rollup processes one level at a time after a BFS-from-leaves.

Common mistakes

  • Popping one node at a time without tracking level boundaries — loses the grouping.
  • Forgetting to handle root == null — return [].
  • Mixing BFS and DFS — pick one.

Follow-up questions

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

  • Zigzag Level Order (LC 103).
  • Binary Tree Level Order Traversal II (bottom-up) (LC 107).
  • How does Snowflake compute plan costs bottom-up?

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 pop the whole level at once?

It gives you the level structure for free. Alternatives like (node, depth) tuples work but require extra state per node.

How does this map to plan-tree costing?

Snowflake's planner computes leaf scan costs first, then bottom-up rolls up through joins/aggregates. BFS-from-leaves gives the right processing order, and within each level the rollup is parallelizable.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →