Level-Order Traversal — Breadth-First Search on Trees

Level-Order Traversal (BFS)

Level-order traversal visits nodes level by level, from top to bottom, left to right within each level. Unlike the three depth-first traversals (in-order, pre-order, post-order), level-order uses a queue instead of a stack or recursion.

Algorithm

LEVELORDER(root):
  if root is NULL: return
  queue = [root]
  while queue is not empty:
    node = queue.dequeue()
    visit(node)
    if node.left:  queue.enqueue(node.left)
    if node.right: queue.enqueue(node.right)

Example

        4
       / \
      2   6
     / \ / \
    1  3 5  7

Level-order result: [4, 2, 6, 1, 3, 5, 7]

Level 0: [4]
Level 1: [2, 6]
Level 2: [1, 3, 5, 7]

Level Grouping Variant

To group nodes by level, track the queue size at the start of each level:

LEVELORDER_GROUPED(root):
  queue = [root]
  result = []
  while queue is not empty:
    level_size = queue.size()
    level = []
    for i in range(level_size):
      node = queue.dequeue()
      level.append(node.value)
      if node.left:  queue.enqueue(node.left)
      if node.right: queue.enqueue(node.right)
    result.append(level)

This produces: [[4], [2, 6], [1, 3, 5, 7]]

Zigzag Level-Order

A popular interview variant alternates the direction at each level: left-to-right at level 0, right-to-left at level 1, and so on. This is solved by reversing every other level in the grouped output.

Time and Space Complexity

• Time: O(n) — every node is visited once
• Space: O(w) — where w is the maximum width (widest level) of the tree; for a complete binary tree this is O(n/2) = O(n)