Breadth-first search

graphtreequeue

Visit every node one step from the start, then every node two steps away, and so on outward. A queue keeps the nodes in the order they were found, which makes breadth-first search the tool for fewest-step paths and level-by-level work.

How to get there

Nearest first, in a queue

1. State the job. Visit every node reachable from a start node, nearest first: every node one edge away, then every node two edges away, and so on. The graph is an adjacency list: graph[node] lists the node’s neighbors.

2. Walk it by hand and find where you get stuck. Take the graph with edges A–B, A–C, B–D, B–E, C–F, E–F, starting at A. One edge away are B and C; two edges away are D and E, through B, and F, through C. Visiting B finds D and E, but they have to wait: C was found earlier and is nearer, so it goes first.

3. Find what to remember. The nodes found but not yet visited, in the order they were found. First found, first visited is a queue. It is depth-first search’s loop with the stack swapped for a queue, and the walk goes wide instead of deep.

4. See why the order is by distance. The queue always holds nodes at some distance d, followed by nodes at distance d + 1. Taking a node at distance d adds only nodes at distance d + 1, at the back. So every node at distance d leaves before any node at d + 1.

5. Mark a node when it is found. F is found from C and again from E. Marking it visited when it joins the queue keeps it from joining twice. The first time a node is found is always through a shortest path, so nothing is lost.

6. Check the cost. Each node joins the queue once and each adjacency list is read once: O(V + E) time, and O(V) space for the queue and the visited set.

The reusable recipe: when the nearest answers matter first, such as the fewest steps or one level at a time, explore with a queue and mark each node when it is found.

Let the queue's meaning write the loop

Variable	Always means, at the top of the loop
`queue`	nodes found but not yet taken, in the order found: nearer nodes ahead of farther ones
`visited`	every node found so far, taken or still waiting in the queue
`order`	the taken nodes, in the order they were taken

Code	What happened	What it keeps true
`visited = {start}`, `queue = deque([start])`	the start is found	it is visited and waiting
`node = queue.popleft()`	the earliest-found node leaves the front	nearer nodes are taken first
`order.append(node)`	the node is taken	`order` gains it
`for neighbor in graph[node]:`	its neighbors are checked
`if neighbor not in visited:`	a neighbor not yet found
`visited.add(neighbor)`, `queue.append(neighbor)`	it is found now	it waits at the back, behind every nearer node
`return order`	the queue is empty	every node reachable from `start` is in `order`, nearest first

Why mark at append, not at popleft. Marking when a node is taken, as depth-first search does, gives the same order here, but a node can then join the queue more than once: on 2,000 random graphs, 923 queued at least one extra copy. Marking at append keeps each node in the queue once.

deque comes from collections. Its popleft takes O(1) time, while list.pop(0) shifts every remaining item and takes O(n).

The method carries over: write down what the queue holds, then each line either takes the front node or adds newly found ones at the back.

On a binary tree, one level at a time

A tree is a graph with no cycles, so every node is found exactly once, from its parent. A LeetCode binary tree stores only left and right children, so the visited set goes away: append the children that exist, and the queue never sees a node twice.

Tree problems often want the nodes grouped by level, such as level-order traversal or a tree’s depth. When a round of the loop starts, the queue holds exactly one whole level: every node at that depth, and nothing deeper. So for _ in range(len(queue)) takes exactly that level, while the children it appends wait behind for the next round. That is bfs_tree.py; on the tree 1, with children 2 and 3, each with two children, it returns [[1], [2, 3], [4, 5, 6, 7]].

The reusable recipe: to work a tree level by level, read the queue’s length at the start of each round, and take exactly that many nodes.

Alternatives compared

Approach	Time	Space	How it works
Queue, mark when found (`bfs_graph.py`)	O(V + E)	O(V)	Take the front node and add its unfound neighbors at the back.
Distances in place of visited (`bfs_shortest_paths.py`)	O(V + E)	O(V)	The same loop with a dictionary: a node gets its distance when found, one more than the node that found it, and being in the dictionary means visited.
Depth-first search	O(V + E)	O(V)	The same loop with a stack: it reaches the same nodes, deepest first, with no distance order.
Dijkstra’s algorithm	O((V + E) log V)	O(V)	For weighted edges: a priority queue takes the node with the smallest total weight so far, where breadth-first search counts edges.

Breadth-first search finds the fewest edges, which is the shortest path only when every edge costs the same. With weights, a path of more edges can be cheaper, and Dijkstra’s algorithm takes over.

Pick breadth-first search when the answer is about distance or levels: the fewest moves, the nearest target, or a tree one level at a time. Pick depth-first search when the answer depends on whole paths or subtrees.

bfs_graph.py

from collections import deque


def bfs(graph: dict[str, list[str]], start: str) -> list[str]:
    visited = {start}
    order = []
    queue = deque([start])

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order

bfs_shortest_paths.py

from collections import deque


def shortest_paths(graph: dict[str, list[str]], start: str) -> dict[str, int]:
    distance = {start: 0}
    queue = deque([start])

    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in distance:
                distance[neighbor] = distance[node] + 1
                queue.append(neighbor)

    return distance

bfs_tree.py

from collections import deque


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
def level_order(root: TreeNode | None) -> list[list[int]]:
    if not root:
        return []
    levels = []
    queue = deque([root])

    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        levels.append(level)

    return levels