Skip to main content

15. Binary Tree Level Order Traversal

mediumAsked at Notion

Traverse a tree level by level using BFS — exactly how Notion's UI renders page hierarchies depth by depth when expanding a workspace sidebar, making this problem a direct stand-in for block-tree breadth expansion.

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

Problem

Given the root of a binary tree, return the level order traversal of its node values — a list of lists, where each inner list contains all values at that depth from left to right.

Constraints

  • 0 <= number of nodes <= 2000
  • -1000 <= Node.val <= 1000

Examples

Example 1

Input
root = [3,9,20,null,null,15,7]
Output
[[3],[9,20],[15,7]]

Explanation: Depth 0: [3]. Depth 1: [9,20]. Depth 2: [15,7].

Example 2

Input
root = [1]
Output
[[1]]

Approaches

1. BFS with queue

Use a queue; at each level, snapshot the current queue size so you know exactly how many nodes belong to that depth before processing children.

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:

2. DFS with depth tracking

Recurse with a depth counter; append to result[depth], growing the array as needed — trades queue allocation for call-stack depth.

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

Notion-specific tips

Notion's sidebar lazily loads nested pages by depth. They want candidates who can explain the queue-size snapshot trick clearly — it demonstrates you can reason about bounded batch sizes, which matters when rendering large workspaces without janking the UI thread.

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

Practice these live with InterviewChamp.AI →