Breadth-First Search Overview

Breadth-First Search (BFS) explores nodes level by level — all neighbors of the current node before going deeper. This guarantees that the first time you reach a node, you reached it via the shortest path (in terms of number of edges).

BFS uses a queue (FIFO). DFS uses a stack (LIFO). That one structural difference determines exploration order.

Tree Level-Order Traversal

from collections import deque

def level_order(root: TreeNode | None) -> list[list[int]]:
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)   # number of nodes at current depth
        level = []

        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)

        result.append(level)

    return result

The inner for loop processes exactly one depth level per outer iteration. After the loop, the queue contains only the next level.

BFS Template

from collections import deque

def bfs(start):
    visited = {start}
    queue = deque([start])

    while queue:
        node = queue.popleft()
        # process node

        for neighbor in get_neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Mark nodes visited before enqueuing (not after dequeuing) to avoid duplicates in the queue.

Tracking Levels (Distance)

To count the minimum number of steps, increment a depth counter after processing each level:

queue = deque([start])
visited = {start}
depth = 0

while queue:
    for _ in range(len(queue)):
        node = queue.popleft()
        if node == target:
            return depth
        for nb in neighbors(node):
            if nb not in visited:
                visited.add(nb)
                queue.append(nb)
    depth += 1

When Do I Use This?

Signal	Use BFS
"Shortest path" in an unweighted graph	Yes
"Minimum steps / moves"	Yes
"Level by level" processing	Yes
Need to explore depth-first / backtrack	Use DFS instead

Practice Problems

Done	Question	Difficulty
	Level Order Sum	Easy
	Rightmost Node	Medium
	Zigzag Level Order	Medium
	Maximum Width of Binary Tree	Medium