Read the four orders off one tree
Take this binary search tree:
8
/ \
3 10
/ \ \
1 6 14
Inorder: 1, 3, 6, 8, 10, 14
Preorder: 8, 3, 1, 6, 10, 14
Postorder: 1, 6, 3, 14, 10, 8
Level: 8, 3, 10, 1, 6, 14
The inorder result is sorted. That is not a coincidence and not a property of this particular tree: inorder traversal of any binary search tree emits its keys in ascending order, because the BST invariant says everything left of a node is smaller and everything right is larger. It is the single most useful fact about BSTs.
Queue versus stack: the whole difference
Every traversal keeps a collection of nodes it has discovered but not yet processed. The type of collection determines the order:
- A stack (last in, first out) gives depth-first. The most recently discovered node is processed next, so the traversal keeps diving deeper. Recursion uses the call stack implicitly, which is why the three DFS orders are usually written recursively.
- A queue (first in, first out) gives breadth-first. The oldest undiscovered node goes next, so the traversal finishes an entire level before starting the one below.
Swap the stack for a queue in a DFS implementation and you have written BFS. Nothing else changes.
Exploring level by level
Breadth-first search visits every node at distance 1 from the start, then every node at distance 2, and so on. It expands outwards in rings.
The mechanism is a queue: take the next node from the front, add its unvisited neighbours to the back. Because the queue is first-in-first-out, nodes are processed in order of distance.
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft() # front of the queue
order.append(node)
for nbr in graph[node]:
if nbr not in visited:
visited.add(nbr) # mark on ENQUEUE, not on dequeue
queue.append(nbr)
return order
The comment on line 11 matters. Marking a node visited when it is added to the queue rather than when it is removed prevents the same node being queued several times, which would otherwise produce exponential blow-up on dense graphs.
Why it finds shortest paths
BFS reaches every node by the fewest possible edges, and the argument is direct: it processes all nodes at distance d before any at distance d+1, so the first time a node is reached is by a shortest path.
That gives shortest paths on unweighted graphs for free. Recording each node's predecessor lets the path be reconstructed:
def shortest_path(graph, start, goal):
prev = {start: None}
queue = deque([start])
while queue:
node = queue.popleft()
if node == goal:
break
for nbr in graph[node]:
if nbr not in prev:
prev[nbr] = node
queue.append(nbr)
if goal not in prev:
return None
path = []
while goal is not None:
path.append(goal)
goal = prev[goal]
return path[::-1]
The crucial limitation: this only works when every edge costs the same. With weights, the fewest-edges path is not the cheapest path, and Dijkstra's algorithm — BFS with a priority queue instead of a plain queue — is required.
BFS against DFS
| | BFS | DFS |
|---|
| Structure | Queue | Stack (or recursion) |
| Explores | Level by level | One branch to the end |
| Shortest path (unweighted) | Yes | No |
| Memory | O(width of the graph) | O(depth of the graph) |
| Finds a nearby target | Quickly | Possibly after a long detour |
| Natural for | Distance, layers, spreading | Connectivity, cycles, backtracking |
The memory row decides the choice on large graphs. BFS holds an entire frontier, which on a wide graph — a social network, where one node may have millions of neighbours — can be enormous. DFS holds only the current path.
So: BFS when you need distance or the target is likely close; DFS when the graph is wide, or when the problem is about connectivity, cycles or exhaustive exploration.
Exploration guide
- Confirm inorder is sorted. Press Random to build a fresh tree, then press Inorder. Whatever shape the tree has, the output sequence comes out in ascending order.
- Watch BFS sweep by level. Press Level (BFS) and follow the highlight. It moves strictly left to right across each row before dropping down — it never descends early, even when a branch is short.
- Compare preorder with postorder. Run Preorder, then Postorder on the same tree. Preorder starts at the root; postorder ends there. That is why copying a tree uses preorder and deleting one uses postorder — you must handle the parent first to copy, and last to delete.
- Change the shape and re-run. Use Node Operations to insert several increasing values, building a lopsided tree. Now the level-order and inorder outputs converge, because a degenerate tree is really a linked list.
What each order is actually for
- Inorder — retrieving BST contents in sorted order, and validating that a tree satisfies the BST property (the output must be strictly increasing).
- Preorder — serialising or copying a tree. The root arrives first, so the structure can be rebuilt as it is read.
- Postorder — deleting or freeing a tree, and evaluating expression trees. Children are fully handled before the parent, so you never free a node you still need.
- Level order — finding the shortest path in an unweighted graph, printing a tree by depth, and any problem where nearer nodes must be considered before further ones.
All four are O(n) time, since each node is visited once. Space differs: DFS costs O(h) for the stack where h is the height, BFS costs O(w) for the queue where w is the widest level. On a balanced tree the bottom level holds about half of all nodes, so BFS uses O(n) memory where DFS uses O(log n).
Where this goes wrong
- Using BFS on a deep, wide tree without thinking about memory. The queue holds an entire level. For a balanced binary tree of a million nodes that is roughly 500,000 entries at the widest point, against DFS’s 20-frame stack.
- Recursing depth-first on a degenerate tree. A tree built from sorted insertions has height n, and the recursion overflows the stack. Either balance the tree or use an explicit stack.
- Forgetting to mark visited nodes on a graph. Trees have no cycles so traversal terminates naturally. Apply the same code to a general graph without a visited set and it loops forever.
- Assuming preorder alone rebuilds a tree. It does not — preorder and postorder each lose the structure. You need inorder plus one of the others, or explicit null markers in the serialisation.
Key takeaway
All four traversals visit every node once in O(n); they differ only in when a node is handled relative to its children, and breadth-first differs from the rest only in using a queue instead of a stack. Inorder yields sorted output on a BST, preorder serialises, postorder frees, and level order finds the nearest thing first. Choose by which of those you need, then check whether O(h) or O(w) memory is the one you can afford.
Where it is used
- Shortest path in unweighted graphs — maze solving, grid navigation, puzzle states.
- Social network degrees of separation — "friends of friends" is BFS to depth 2.
- Web crawling — crawl by depth from the seed pages so shallow, important pages are fetched first.
- Level-order tree traversal — printing a tree row by row, or finding its width.
- Connected components — run BFS from each unvisited node.
- Bipartite checking — two-colour the graph by level; an edge within a level means it is not bipartite.
- Flood fill — the paint-bucket tool, and region labelling in image processing.
- Broadcast and infection modelling — spread happens in rings, which is exactly BFS's shape.
On a grid, the neighbour generation is the only change:
def grid_bfs(grid, start):
rows, cols = len(grid), len(grid[0])
dist = {start: 0}
q = deque([start])
while q:
r, c = q.popleft()
for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols \
and grid[nr][nc] != "#" and (nr, nc) not in dist:
dist[(nr, nc)] = dist[(r, c)] + 1
q.append((nr, nc))
return dist
Variants worth knowing
Multi-source BFS. Seed the queue with several starting nodes at distance 0. The result gives each node its distance to the nearest source, in one pass. This is how "distance to the nearest hospital" or "how long until the whole grid is infected" problems are solved — and doing it as separate BFS runs per source is the common inefficient mistake.
0-1 BFS. When edges have weights of only 0 or 1, a double-ended queue works: push 0-weight neighbours to the front and 1-weight to the back. O(V+E), avoiding Dijkstra's log factor.
Bidirectional BFS. Search forwards from the start and backwards from the goal, stopping when they meet. If the branching factor is b and the distance d, this reduces the work from roughly b^d to 2b^(d/2) — a large saving on long paths.
BFS on implicit graphs. The graph need not exist as a data structure. Puzzle states (Rubik's cube, sliding tiles, word ladders) are generated on demand, and BFS explores them by move count.
Complexity and practical notes
Time: O(V + E) — every node dequeued once, every edge examined once.
Space: O(V) for the visited set, plus the queue, whose maximum size is the graph's widest level.
Three implementation details that matter:
Use collections.deque, not a list. list.pop(0) is O(n) because it shifts every element, turning the whole traversal into O(V²). This is the most common BFS performance bug.
Mark visited on enqueue. As above — otherwise nodes are queued repeatedly.
Store distances in the visited structure. A dictionary from node to distance serves as both the visited set and the result, which is simpler than maintaining two.
The queue is the only difference, and it changes the answer
BFS and DFS are the same seven lines with one substitution: take the next node from the front of the collection or from the back. That single change is what makes one of them find shortest paths and the other not, and the clearest way to see it is to run both from the same code.
Questions people ask
Does BFS work on weighted graphs? Not for shortest paths — it minimises edge count, not cost. Use Dijkstra, or 0-1 BFS if weights are only 0 and 1.
Why a queue rather than a stack? The queue's first-in-first-out order is what produces level-by-level exploration. A stack gives DFS.
Can BFS be recursive? Not naturally — recursion gives a stack, which is DFS. BFS needs an explicit queue.
What if the graph has cycles? The visited set handles them. Without it, BFS loops forever.
How do I find the shortest path itself? Record each node's predecessor and walk backwards from the goal.
Which uses less memory? DFS on wide graphs, BFS on deep ones. The frontier width against the path depth.
Recap in one screen
- A queue makes exploration proceed level by level, in order of distance from the start.
- That gives shortest paths on unweighted graphs, recorded via predecessors.
- Mark nodes visited when enqueued, and use
deque — list.pop(0) makes it quadratic. - Memory is the frontier width, which can be enormous on wide graphs where DFS is cheaper.
- Multi-source BFS answers "distance to the nearest" in one pass; bidirectional BFS halves the exponent.