LeetCode 102 · BFS · Queue

Binary Tree Level Order Traversal

MediumReturn node values grouped level by level, top to bottom.
Given the root of a binary tree, return the level-order traversal of its nodes' values — the values grouped by depth, read left to right, from the top level down.

Walkthrough

trees:
LeetCode array format · use null for a missing child
1
function levelOrder(root) {
2
  const result = [];
3
  if (!root) return result;
4
  const queue = [root];
◄
5
  while (queue.length) {
6
    const level = [];
7
    for (let n = queue.length; n > 0; n--) {
8
      const node = queue.shift();
9
      level.push(node.val);
10
      if (node.left) queue.push(node.left);
11
      if (node.right) queue.push(node.right);
12
    }
13
    result.push(level);
14
  }
15
  return result;
16
}
levels = 0queue = 1
3920157
queue (front → back)
3
result
[]
STEP 0 / 9 · line 4
Start
Seed the queue with the root. We process the tree breadth-first, one full level per round.

Intuition

Level order is a breadth-first walk: finish every node at depth 0 before touching depth 1, and so on.

A queue produces that order for free — it always hands back the oldest-enqueued node first (FIFO).

The trick to grouping by level is to record the queue’s size at the start of each round; exactly that many nodes make up the current level.

Dequeue that many nodes, collect their values, and enqueue their children for the next round.

The algorithm

  1. 01If the tree is empty, return an empty list.
  2. 02Put the root in a queue.
  3. 03While the queue is non-empty, snapshot its length — that many nodes form the current level.
  4. 04Dequeue each one, append its value to the level, and enqueue its non-null children.
  5. 05Push the finished level onto the result and repeat.

Reference implementation

1
function levelOrder(root) {
2
  const result = [];
3
  if (!root) return result;
4
  const queue = [root];
5
  while (queue.length) {
6
    const level = [];
7
    for (let n = queue.length; n > 0; n--) {
8
      const node = queue.shift();
9
      level.push(node.val);
10
      if (node.left) queue.push(node.left);
11
      if (node.right) queue.push(node.right);
12
    }
13
    result.push(level);
14
  }
15
  return result;
16
}

Complexity

Time
O(n) — every node is enqueued and dequeued exactly once.
Space
O(n) — the queue holds up to the widest level of the tree.