Skip to main content
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)
·
O(n)

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 traversal using queue
3
0
9
1
20
2
15
3
7
4
Level 0[3]
1/3

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.