Binary Tree Level Order Traversal

The problem

Given the root of a binary tree, return its node values level by level, as a list of lists.

Example: for the tree below, the answer is [[3], [9, 20], [15, 7]].

Depth-first traversals (pre/in/post-order) dive down a branch before visiting siblings — the wrong shape here. "Level by level" calls for breadth-first search: visit all nodes at distance d before any node at distance d+1. A queue does exactly that.

Approach 1 — DFS with a depth parameter

BFS is the natural fit, but DFS can also produce level groupings: pass the depth down the recursion and append each node to result[depth].

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
}

Time: O(n). Space: O(h) recursion stack. Works because visiting left before right keeps each level list in left-to-right order. Good to know — but the queue version below is the one that generalizes to "zigzag", "right side view", and "rotting oranges"-style problems.

Approach 2 — BFS with a queue (the standard)

Push the root. Each loop iteration processes one full level: snapshot the current queue length, pop exactly that many nodes, and push their children (which form the next level).

function levelOrder(root) {
  if (!root) return []

  const result = []
  const queue = [root]

  while (queue.length > 0) {
    const levelSize = queue.length // snapshot BEFORE pushing children
    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
}

Time: O(n) — each node enters and leaves the queue once. Space: O(w), the tree's maximum width (up to n/2 for a bushy tree).

The levelSize snapshot is the entire trick: without it, children pushed mid-level would bleed into the current level's loop.

Dry run

Tree: 3 with children 9, 20; 20 with children 15, 7.

Iteration	Queue at start	levelSize	Popped	Pushed	result
1	[3]	1	3	9, 20	[[3]]
2	[9, 20]	2	9, then 20	15, 7 (from 20)	[[3], [9, 20]]
3	[15, 7]	2	15, then 7	nothing	[[3], [9, 20], [15, 7]]
4	[]	—	—	—	queue empty — done

Edge cases

Empty tree → [] (the early return).
Skewed tree (every node has one child) → each level is a single-element list; the queue never holds more than one node.
Array.prototype.shift() is O(n) in the worst case; for very large trees use an index pointer into the array instead of shifting. Interviewers rarely mind, but knowing it is a plus.
Variants that reuse this exact skeleton: Zigzag Level Order (alternate reversing level), Right Side View (keep the last node per level), Average of Levels.