Overview#

Level-order traversal is BFS on a binary tree. It visits nodes layer by layer from top to bottom and from left to right, making it ideal for problems involving “each level.”

Unlike recursive DFS, level-order traversal uses a queue to maintain the nodes waiting to be visited. The first-in-first-out property of the queue maps exactly to the level order of the tree.

Common variants include: per-level node lists, zigzag traversal, right side view, maximum value per level, and average value per level.

Prerequisites

• Binary tree: level-order traversal visits nodes by depth
• Queue: first-in-first-out guarantees same-level ordering
• BFS: level-order traversal is breadth-first search on a tree

Problem Definition#

Given a binary tree:

1
      3
2
     / \
3
    9   20
4
       /  \
5
      15   7

The level-order traversal result is:

1
[
2
  [3],
3
  [9, 20],
4
  [15, 7]
5
]

The key question is: how do you know how many nodes are in the current level?

The answer is: before processing each level, record the current length of the queue. That length is the number of nodes in the current level.

Core Principle: Step-by-Step Diagram#

Initially, the queue contains only the root node:

1
queue: [3]

Process level 1, pop 3, and enqueue its children:

1
result: [[3]]
2
queue: [9, 20]

When processing level 2, first record levelSize = 2 and process only those two nodes. The children they produce belong to the next level:

1
result: [[3], [9, 20]]
2
queue: [15, 7]

The queue naturally guarantees top-to-bottom order, while levelSize defines the boundary of each level.

Detailed Algorithm Steps#

Standard level-order traversal:

1. If the root node is null, return an empty array;
2. Enqueue the root node;
3. While the queue is not empty, record the current queue length;
4. Loop through all nodes in the current level;
5. Pop a node and record its value;
6. Enqueue its non-null left and right children;
7. After the current level is fully processed, add the level result to the answer.

Complexity:

• Time complexity O(n), each node is enqueued and dequeued once;
• Space complexity O(w), where w is the maximum width of the tree.

TypeScript Implementation#

1
class TreeNode<T> {
2
  constructor(
3
    public value: T,
4
    public left: TreeNode<T> | null = null,
5
    public right: TreeNode<T> | null = null,
6
  ) {}
7
}

1
function levelOrder<T>(root: TreeNode<T> | null): T[][] {
2
  if (root === null) return [];
3

4
  const result: T[][] = [];
5
  const queue: TreeNode<T>[] = [root];
6
  let head = 0;
7

8
  while (head < queue.length) {
9
    const levelSize = queue.length - head;
10
    const level: T[] = [];
11

12
    for (let i = 0; i < levelSize; i++) {
13
      const node = queue[head++];
14
      level.push(node.value);
15

16
      if (node.left) queue.push(node.left);
17
      if (node.right) queue.push(node.right);
18
    }
19

20
    result.push(level);
21
  }
22

23
  return result;
24
}

1
function rightSideView<T>(root: TreeNode<T> | null): T[] {
2
  return levelOrder(root).map(level => level[level.length - 1]);
3
}

1
function zigzagLevelOrder<T>(root: TreeNode<T> | null): T[][] {
2
  const levels = levelOrder(root);
3

4
  for (let i = 1; i < levels.length; i += 2) {
5
    levels[i].reverse();
6
  }
7

8
  return levels;
9
}

Engineering Optimization: Don’t Shift the Queue Frequently#

Many examples write it like this:

1
const node = queue.shift();

This is fine with small data, but shift moves array elements, and frequent calls may incur O(n) cost. A more robust approach is to use a head pointer:

1
const node = queue[head++];

This turns dequeue into O(1), which is especially suitable for trees or graphs with a large number of nodes.

Applications and Limitations#

Summary#

• Level-order traversal is BFS on a binary tree.
• The queue guarantees visit order, and levelSize defines level boundaries.
• Each node is enqueued and dequeued only once, so the time complexity is O(n).
• Replacing shift with a head pointer avoids the cost of array shifting.
• Level-order traversal is suitable for all problems involving “per-level statistics or observation.”