BFS Queue

Level-Order Traversal

Process a tree level by level. At each step, note the queue size (= nodes at this level), process exactly that many nodes, and their children form the next level. Useful for level averages, zigzag traversal, etc.

O(n)

say this out loud

The question is per level, so BFS with a queue and I snapshot the queue size at the start of each round to keep levels separate.

How It Works

Level-order traversal visits a tree one depth at a time, and a queue makes the levels fall out naturally. Enqueue the root, then loop: record the queue's current size (that is exactly the number of nodes on this level) dequeue that many nodes, process each, and enqueue their children. When the inner loop ends, the queue holds precisely the next level.

The size-snapshot trick is what separates levels; without it you get a flat BFS order with no level boundaries. Every node is enqueued and dequeued once, so traversal is O(n) time with O(w) space, where w is the tree's maximum width, up to n/2 for a complete tree's bottom level.

Step-by-Step Visualization

Level order over a tree with 3 at the root, 9 and 20 below it, and 15 and 7 under the 20

queue[3]

1/8

Code

Java

static List<List<Integer>> levelOrder(TreeNode root) {
  if (root == null) return new ArrayList<>();
  List<List<Integer>> result = new ArrayList<>();
  Queue<TreeNode> queue = new LinkedList<>();
  queue.add(root);

  while (!queue.isEmpty()) {
    List<Integer> level = new ArrayList<>();
    int size = queue.size();
    for (int i = 0; i < size; i++) {
      TreeNode node = queue.poll();
      level.add(node.val);
      if (node.left != null) queue.add(node.left);
      if (node.right != null) queue.add(node.right);
    }
    result.add(level);
  }
  return result;
}

Tips & Gotchas

1Same as tt-level: BFS with queue, process level by level

2Track queue size at start of each level

3Useful for zigzag, right side view, level averages

Practice Problems

1Binary Tree Level Order Traversal
2Binary Tree Zigzag Level Order Traversal
3Binary Tree Right Side View
4Average of Levels in Binary Tree

About the BFS Queue Pattern

BFS explores nodes level by level using a queue. Enqueue the starting node, then repeatedly: dequeue a node, process it, and enqueue all its unvisited neighbors. This guarantees you visit nodes in order of their distance from the start.

Key insight

BFS = queue. If you need shortest path in an unweighted graph or level-order traversal, reach for a queue. Monotonic deques solve sliding window extremes in O(n).

Common Queue / Deque Interview Problems

Binary Tree Level Order Traversal
Sliding Window Maximum
Rotting Oranges
Shortest Path in Binary Matrix
Implement Queue using Stacks

Frequently Asked Questions

How do I get zigzag order without a second data structure?

Keep the queue-based traversal unchanged and only alter how each level's list is built: on alternating levels, insert values at the front of the level list (or reverse it after filling). Reversing the actual traversal order is unnecessary and error-prone.

Can DFS produce a level-order grouping too?

Yes. Recurse with a depth parameter and append each node's value to result[depth]. It yields the same grouped output in O(n), but uses O(h) call-stack space instead of O(w) queue space, so it can be preferable on very wide, shallow trees.