Traverse a tree level by level the way breadth-first search does, and compare it against the depth-first orders on the same nodes.
Overview
Four ways to visit every node
A traversal visits every node exactly once. A tree is not linear, so there is no single obvious order — and the four standard orders differ only in when a node is processed relative to its children.
Inorder — left subtree, node, right subtree.
Preorder — node, left subtree, right subtree.
Postorder — left subtree, right subtree, node.
Level order (BFS) — every node at depth 0, then every node at depth 1, and so on.
The first three are depth-first: they plunge to the bottom of one branch before considering the next. Only the fourth is breadth-first.
CANVAS VIEW
Breadth First Search: A Practical Guide
Visit a tree level by level rather than branch by branch. A queue is the only thing separating breadth-first search from its depth-first siblings - and that one choice decides everything about the order.
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.
example_01.pyPython
# Two routes from A to G: a short one through C, and a long one through
# B. They are listed so that a stack reaches the long one first -- which
# is the case that separates the two searches.
GRAPH = {
"A": ["C", "B"],
"C": ["G"], # A -> C -> G, two edges
"B": ["D"],
"D": ["E"],
"E": ["G"], # A -> B -> D -> E -> G, four edges
"G": [],
}
from collections import deque
def search(graph, start, goal, breadth_first):
frontier = deque([(start, [start])])
seen = {start}
order = []
while frontier:
node, path = frontier.popleft() if breadth_first else frontier.pop()
order.append(node)
if node == goal:
return order, path
for nxt in graph[node]:
if nxt not in seen:
seen.add(nxt)
frontier.append((nxt, path + [nxt]))
return order, None
for label, bf in (("BFS (popleft)", True), ("DFS (pop)", False)):
order, path = search(GRAPH, "A", "G", bf)
print("%-15s visits %s" % (label, " ".join(order)))
print("%-15s path to G: %s (%d edges)" % ("", " -> ".join(path), len(path) - 1))
# Both find G. BFS found it in two edges and DFS in four, on the same
# graph with the same code -- and that is not luck: BFS reaches every node
# by the fewest edges possible, because it finishes everything at distance
# 1 before it starts on distance 2. DFS committed to the first branch it
# entered and took the route that branch happened to offer.
#
# Watch the frontier to see why. BFS explores in complete rings:
def levels(graph, start):
frontier, seen, d = deque([start]), {start}, {start: 0}
order = []
while frontier:
node = frontier.popleft()
order.append((node, d[node]))
for nxt in graph[node]:
if nxt not in seen:
seen.add(nxt)
d[nxt] = d[node] + 1
frontier.append(nxt)
return order
print()
print("distance from A, in the order BFS settles them:")
for node, dist in levels(GRAPH, "A"):
print(" %s at distance %d" % (node, dist))
# The distances come out non-decreasing: 0, 1, 1, 2, 2, 3. A node is
# never settled before anything closer to the start, which is exactly the
# invariant that makes the first time you reach a node also the best time.
#
# DFS has no such property. It commits to one branch and can arrive at a
# node the long way round:
order, path = search(GRAPH, "A", "G", False)
print()
bfs_order, bfs_path = search(GRAPH, "A", "G", True)
print("DFS reached G via %s -- %d edges, when %d were available."
% (" -> ".join(path), len(path) - 1, len(bfs_path) - 1))
# The catch: this only holds when every edge costs the same. BFS counts
# EDGES, not distance. Give the edges different weights and the fewest-hop
# route stops being the cheapest one, which is the gap Dijkstra's
# algorithm exists to fill -- it is BFS with a priority queue instead of
# a plain one, so it settles nodes by total cost rather than hop count.
Output
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.
Run it in Python
BFS printed level by level, then used for what it is actually for: the shortest path in an unweighted graph. The queue contents are shown at every step so the frontier is visible.
bfs.pyPython 3
# Breadth-first search: explore everything one step away, then two, then...
from collections import deque
graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E", "G"],
"G": ["F"],
}
def bfs(graph, start):
visited = {start} # marked when ENQUEUED, not when dequeued
queue = deque([start])
order, parent, dist = [], {start: None}, {start: 0}
while queue:
print(f" queue: {list(queue)}")
node = queue.popleft() # popleft = FIFO = breadth-first
order.append(node)
for neighbour in graph[node]:
if neighbour not in visited:
visited.add(neighbour)
parent[neighbour] = node
dist[neighbour] = dist[node] + 1
queue.append(neighbour)
return order, parent, dist
print("BFS from A:")
order, parent, dist = bfs(graph, "A")
print()
print("visit order:", " -> ".join(order))
print()
levels = {}
for node, d in dist.items():
levels.setdefault(d, []).append(node)
for d in sorted(levels):
print(f" {d} step(s) from A: {levels[d]}")
# Rebuild the path by walking parents backwards from the target.
target = "G"
path, node = [], target
while node is not None:
path.append(node)
node = parent[node]
print()
print(f"shortest path A -> {target}:", " -> ".join(reversed(path)),
f"({dist[target]} edges)")
Output
How the code works
queue = deque([start])A deque, not a list: list.pop(0) is O(n) because it shifts every remaining item. On a large graph that alone turns a linear traversal quadratic.
visited.add(neighbour) # on enqueueMarking on enqueue rather than on dequeue is the difference between BFS and a slow disaster. Mark late and a node with three neighbours already in the queue gets added three times.
node = queue.popleft()First in, first out. Change this one call to pop() and the same twelve lines become depth-first search — the container is the algorithm.
dist[neighbour] = dist[node] + 1Because nodes are dequeued in order of distance, the first time BFS reaches a node is necessarily by a shortest path. This is why BFS solves shortest paths on unweighted graphs and Dijkstra is not needed.
while node is not None: path.append(node)The parent map is a tree rooted at the start, so the path is recovered by walking up it. Storing the whole path per node instead would cost O(V) memory per node for no benefit.
Change one thing
Change popleft() to pop(). The visit order becomes depth-first and the distances stop being shortest paths.
Move visited.add to just after popleft(), then print the queue length. Nodes appear more than once — the classic BFS bug.
Add the edge "A": ["B", "C", "G"]. The path to G drops to one edge, and the level listing rearranges itself.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
Turning BFS into DFS requires changing:
FIFO gives breadth-first, LIFO gives depth-first. The rest of the loop is identical, which is the clearest way to see that the container is the algorithm.
Why does the code mark a node visited when it is enqueued rather than when it is dequeued?
Marking late lets the same node be queued repeatedly before it is ever processed, which blows up the queue on dense graphs.
BFS gives shortest paths on an unweighted graph because:
The frontier expands one full level at a time. On weighted graphs that no longer holds and you need Dijkstra.
Cheat sheet
Breadth First Search
A traversal visits every node exactly once. A tree is not linear, so there is no single obvious order — and the four standard orders differ only in when a node is processed relative to its children.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.