Frontend Beauty
ESC

Type to search the knowledge base.

Binary Tree Level Order

BFS level-order traversal of a binary tree — queue sizing, empty levels, and the recursive DFS variant interviewers compare.

intermediate3 min read
  • dsa
  • tree
  • interview
  • Google
  • Meta
  • Amazon
  • Microsoft

The problem

Given a binary tree, return node values level by level, left to right. Each level is its own array.

      3
     / \
    9  20
      /  \
     15   7

Output: [[3], [9, 20], [15, 7]]

This is BFS on a tree. Same pattern as “print each generation of a DOM subtree” or “process React fiber-ish levels” — queue + process a batch.

Brute / awkward: collect with depth map then sort

DFS with depth, push into Map<depth, vals[]>, then dump keys in order. Works, but you’re simulating BFS with extra bookkeeping.

function levelOrderDfsMap(root: TreeNode | null): number[][] {
  const levels: number[][] = [];
  function dfs(node: TreeNode | null, d: number) {
    if (!node) return;
    if (!levels[d]) levels[d] = [];
    levels[d].push(node.val);
    dfs(node.left, d + 1);
    dfs(node.right, d + 1);
  }
  dfs(root, 0);
  return levels;
}
Time O(n)
Space O(n) + O(h) stack

Correct and fine. Interviewers often want the queue form as the primary answer.

Optimal mental model: BFS with level size

  1. Queue starts with root.
  2. While queue non-empty: size = queue.length is the current level width.
  3. Pop exactly size nodes; push their children for the next level.
  4. Append that level’s values.
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const res: number[][] = [];
  const q: TreeNode[] = [root];

  while (q.length) {
    const size = q.length;
    const level: number[] = [];
    for (let i = 0; i < size; i++) {
      const node = q.shift()!;
      level.push(node.val);
      if (node.left) q.push(node.left);
      if (node.right) q.push(node.right);
    }
    res.push(level);
  }
  return res;
}
Time O(n)
Space O(w) queue width, worst O(n)

JS note: shift() is O(n) on arrays. For interviews it’s usually accepted; for production BFS on huge graphs use an index pointer or a real deque.

// avoid shift — index cursor
function levelOrderFast(root: TreeNode | null): number[][] {
  if (!root) return [];
  const res: number[][] = [];
  const q: TreeNode[] = [root];
  let head = 0;

  while (head < q.length) {
    const size = q.length - head;
    const level: number[] = [];
    for (let i = 0; i < size; i++) {
      const node = q[head++];
      level.push(node.val);
      if (node.left) q.push(node.left);
      if (node.right) q.push(node.right);
    }
    res.push(level);
  }
  return res;
}

Edge cases

  • null root → []
  • Single node → [[val]]
  • Skewed tree → each level length 1
  • Full complete tree → last level is widest

Variants

  • Zigzag level order — reverse alternate levels
  • Right side view — last node of each level
  • Average of levels — sum / count per level
  • Connect next pointers (perfect tree) — same BFS skeleton

Interview delivery

  1. Empty tree base case.
  2. BFS + capture level size before expanding.
  3. Mention DFS-with-depth as alternative.
  4. O(n) time, O(n) space.
  5. Optional: shift cost in JS.

Further reading