TreesLesson 4

Tree Traversals — BFS

Level-order traversal using a queue — visit nodes level by level, left to right. The foundation for BFS on graphs.

What Is It?

Breadth-first search (BFS) on a tree visits nodes level by level. First the root. Then all nodes one step away. Then all nodes two steps away. And so on.

This is also called level-order traversal — you process the tree one layer at a time.

The key tool is a queue (first-in, first-out). You add the root to the queue, then repeatedly take a node out, process it, and add its children to the back of the queue. Because the queue is FIFO, nodes at shallower levels always get processed before nodes at deeper levels.

Analogy

Ripples in a Pond

Drop a stone in a pond. The ripples spread outward in rings — the first ring is closest, then the second ring, then the third. Every point at distance 1 from the center gets wet before any point at distance 2.

BFS works exactly like that. The root is the stone. Nodes at depth 1 are the first ring. Nodes at depth 2 are the second ring. You process each ring completely before moving to the next.

Contrast this with DFS, which would follow one ripple all the way to the edge of the pond before coming back for the others.

How It Works

The Algorithm

pseudocode

function levelOrder(root):
    if root is null:
        return []
    
    queue = new Queue()
    queue.enqueue(root)
    result = []
    
    while queue is not empty:
        node = queue.dequeue()
        result.append(node.data)
        
        if node.left is not null:
            queue.enqueue(node.left)
        if node.right is not null:
            queue.enqueue(node.right)
    
    return result

That's it. Add root. Loop: take one out, add its children to the back. Repeat.

Step-by-Step Trace

pseudocode

pseudocode

Step | Action            | Queue (front -> back) | Output
─────|───────────────────|───────────────────────|──────────
  0  | Enqueue root 1    | [1]                   |
  1  | Dequeue 1         | []                    | 1
     | Enqueue 2, 3      | [2, 3]                |
  2  | Dequeue 2         | [3]                   | 1, 2
     | Enqueue 4, 5      | [3, 4, 5]             |
  3  | Dequeue 3         | [4, 5]                | 1, 2, 3
     | Enqueue 6         | [4, 5, 6]             |
  4  | Dequeue 4         | [5, 6]                | 1, 2, 3, 4
     | No children       |                       |
  5  | Dequeue 5         | [6]                   | 1, 2, 3, 4, 5
     | Enqueue 7         | [6, 7]                |
  6  | Dequeue 6         | [7]                   | 1, 2, 3, 4, 5, 6
     | No children       |                       |
  7  | Dequeue 7         | []                    | 1, 2, 3, 4, 5, 6, 7
     | Queue empty, done |                       |
BFS result: 1, 2, 3, 4, 5, 6, 7

All of depth 0 (node 1), then depth 1 (nodes 2, 3), then depth 2 (nodes 4, 5, 6), then depth 3 (node 7).

Why a Queue and Not a Stack?

The queue is what makes BFS work. If you swapped it for a stack (last-in, first-out), you'd get depth-first behavior instead:

pseudocode

Queue (FIFO):  Dequeue 1 -> process 2 (was enqueued first)
               -> Level by level
Stack (LIFO):  Pop 1 -> process 3 (was pushed last)
               -> Depth-first, wrong order

FIFO guarantees shallower nodes are always processed before deeper ones.

Variant: Processing Level by Level

Often you need to group nodes by level — for example, to find the max value on each level. The trick: snapshot the queue size at the start of each level. That count tells you exactly how many nodes belong to the current level.

pseudocode

function levelOrderByLevel(root):
    if root is null:
        return []
    
    queue = new Queue()
    queue.enqueue(root)
    levels = []
    
    while queue is not empty:
        levelSize = queue.size()      // How many nodes are at this level?
        currentLevel = []
        
        for i = 0 to levelSize - 1:
            node = queue.dequeue()
            currentLevel.append(node.data)
            
            if node.left is not null:
                queue.enqueue(node.left)
            if node.right is not null:
                queue.enqueue(node.right)
        
        levels.append(currentLevel)
    
    return levels

Trace on the same tree:

pseudocode

Iteration 1: levelSize = 1
  Dequeue 1, enqueue 2 and 3
  currentLevel = [1]
  Queue: [2, 3]
Iteration 2: levelSize = 2
  Dequeue 2, enqueue 4 and 5
  Dequeue 3, enqueue 6
  currentLevel = [2, 3]
  Queue: [4, 5, 6]
Iteration 3: levelSize = 3
  Dequeue 4 (no children)
  Dequeue 5, enqueue 7
  Dequeue 6 (no children)
  currentLevel = [4, 5, 6]
  Queue: [7]
Iteration 4: levelSize = 1
  Dequeue 7 (no children)
  currentLevel = [7]
Result: [[1], [2, 3], [4, 5, 6], [7]]

Key insight: snapshot queue.size() before the inner loop. All nodes you enqueue during this iteration belong to the NEXT level.

Common BFS Patterns

Once you know level-order traversal, many problems follow the same template:

Maximum value at each level:

pseudocode

function maxPerLevel(root):
    queue = new Queue()
    queue.enqueue(root)
    result = []
    while queue is not empty:
        levelSize = queue.size()
        levelMax = -INFINITY
        for i = 0 to levelSize - 1:
            node = queue.dequeue()
            levelMax = max(levelMax, node.data)
            if node.left: queue.enqueue(node.left)
            if node.right: queue.enqueue(node.right)
        result.append(levelMax)
    return result

Rightmost node at each level (right side view):

pseudocode

function rightSideView(root):
    queue = new Queue()
    queue.enqueue(root)
    result = []
    while queue is not empty:
        levelSize = queue.size()
        for i = 0 to levelSize - 1:
            node = queue.dequeue()
            if i == levelSize - 1:     // Last node in this level
                result.append(node.data)
            if node.left: queue.enqueue(node.left)
            if node.right: queue.enqueue(node.right)
    return result

Shallowest leaf (minimum depth):

pseudocode

function minDepth(root):
    if root is null: return 0
    queue = new Queue()
    queue.enqueue(root)
    depth = 0
    while queue is not empty:
        depth = depth + 1
        levelSize = queue.size()
        for i = 0 to levelSize - 1:
            node = queue.dequeue()
            if node.left is null and node.right is null:
                return depth       // First leaf found is the shallowest
            if node.left: queue.enqueue(node.left)
            if node.right: queue.enqueue(node.right)
    return depth

BFS finds the shallowest leaf first because it always finishes shallower levels before going deeper.

BFS vs. DFS: When to Use Which

Use BFS when

You need level-by-level info
You want the shortest path
You need the shallowest answer
The answer is near the root
You need to process by layers

Breadth-First Search

Use DFS when

You need to explore full paths
You want sorted order (inorder)
Memory is limited
The answer is deep in the tree

Depth-First Search

Time and Space

Time: O(n) — every node is enqueued and dequeued exactly once
Space: O(w) where w is the maximum width of the tree. For a wide, balanced tree, that can be O(n). For a tall, thin tree, it's O(1).

Compared to DFS: DFS space is O(h) (the height). For a balanced tree, DFS uses O(log n) space while BFS might use O(n). For a very tall skinny tree, DFS uses O(n) while BFS uses O(1).

From Trees to Graphs

BFS on a tree is almost identical to BFS on a graph. The only difference: graphs can have cycles, so you need a visited set to avoid processing the same node twice. Trees have no cycles, so no visited set is needed.

Tree BFS

queue.enqueue(root)
while queue not empty:
node = queue.dequeue()
process(node)
enqueue children

No visited set needed — trees have no cycles

simpler version

Graph BFS

queue.enqueue(start)
visited.add(start)
while queue not empty:
node = queue.dequeue()
process(node)
for each neighbor:
if not visited: enqueue & mark

Visited set prevents revisiting nodes in cycles

adds one extra step

Master tree BFS first — the graph version is just one small addition.

Examples

Example 1: Level-order on a balanced tree

pseudocode

         10
        /  \
       5    15
      / \   / \
     3   7 12  20
Level order: 10, 5, 15, 3, 7, 12, 20
By level: [[10], [5, 15], [3, 7, 12, 20]]

Example 2: Level-order on an unbalanced tree

pseudocode

     1
      \
       2
      / \
     3   4
          \
           5
Level order: 1, 2, 3, 4, 5
By level: [[1], [2], [3, 4], [5]]
Queue trace:
  Start: [1]
  Dequeue 1, enqueue 2   -> [2]
  Dequeue 2, enqueue 3,4 -> [3, 4]
  Dequeue 3 (no kids)    -> [4]
  Dequeue 4, enqueue 5   -> [5]
  Dequeue 5 (no kids)    -> []

Example 3: Zigzag level-order

A common interview variant — alternate left-to-right and right-to-left each level:

pseudocode

function zigzagLevelOrder(root):
    queue = new Queue()
    queue.enqueue(root)
    result = []
    leftToRight = true
    while queue is not empty:
        levelSize = queue.size()
        currentLevel = []
        for i = 0 to levelSize - 1:
            node = queue.dequeue()
            currentLevel.append(node.data)
            if node.left: queue.enqueue(node.left)
            if node.right: queue.enqueue(node.right)
        if not leftToRight:
            reverse(currentLevel)
        result.append(currentLevel)
        leftToRight = not leftToRight
    return result
         1
        / \
       2   3
      / \   \
     4   5   6
Result: [[1], [3, 2], [4, 5, 6]]

Common Mistakes

Using a stack instead of a queue. A stack gives DFS behavior. Always use a queue (FIFO) for level-order traversal.

Not snapshotting the queue size. If you check queue.size() inside the inner loop, the size keeps changing as you add children. Capture it BEFORE the loop starts.

Enqueuing null children. Always check if node.left is not null before enqueuing. Enqueueing null will cause a crash when you try to process it.

Forgetting the empty tree check. If root is null and you try to enqueue it, you'll crash in the first iteration. Always guard against null root.

Confusing BFS space with DFS space. BFS space is proportional to the width of the tree. DFS space is proportional to the height. A wide balanced tree uses more BFS memory, not less.

Best Practices

Use the level-size snapshot pattern whenever you need to group nodes by level — it's the most useful BFS template
When a problem asks for "shortest path" or "minimum depth", think BFS first — it finds shallow answers before deep ones
For simple traversal without level grouping, the basic queue version is cleaner
Learn tree BFS first, then graph BFS — it's just one extra concept (visited set) on top of what you already know

Tree Traversals — DFS How Heaps Work