A tree is just a graph with an extra rule (no cycles, one path to any node). Dropping that rule is what unlocks graphs — and the traversal patterns look almost identical, with one crucial addition.
5 min read
A tree (from its own lesson) is a graph with two restrictions: no cycles, and exactly one path between any two nodes. A graph drops both restrictions — nodes (vertices) can connect to any other nodes via edges, connections can form cycles, and there can be multiple paths — or no path at all — between two given nodes. Trees are graphs; not every graph is a tree. A social network (who follows whom), a road map (which intersections connect to which), and a dependency graph (which package requires which other package) are all naturally graphs, not trees — there's no single "root," and cycles are often normal (two friends can follow each other; two intersections can connect both ways).
An edge can be undirected (the connection goes both ways, like a friendship) or directed (one-way, like a "follows" relationship or a one-way street). An edge can also carry a weight — a cost, distance, or time associated with traversing it — or be unweighted, where every edge is treated as equally costly. These are independent choices: a graph can be directed and weighted (flights between cities, with cost), undirected and unweighted (a simple friend network), or any other combination — recognizing which one you're looking at determines which algorithms even apply.
graph = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "D"],
"D": ["B", "C", "E"],
"E": ["D"],
}The adjacency list — a dict mapping each node to a list of its neighbors — is the standard representation for most real graph problems, because it's compact and directly answers "what does this node connect to" without wasted space. The alternative, an adjacency matrix (a 2D grid where matrix[i][j] is 1 if an edge exists between node i and j), makes "are these two specific nodes connected" an O(1) lookup, but wastes memory on sparse graphs — a graph with 10,000 nodes and only 20,000 edges would need a 10,000×10,000 matrix (mostly zeros) versus an adjacency list sized to the actual number of edges.
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
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 orderBreadth-first search visits all of a node's immediate neighbors before moving on to their neighbors — level by level, outward from the start, exactly the shape covered in the stacks-and-queues lesson. A queue (FIFO) is what enforces this: nodes are processed in the exact order they were discovered, so every node at distance 1 from start is visited before any node at distance 2. The visited set is the one addition graphs need beyond what tree traversal required — since a graph can contain cycles, without tracking visited nodes, bfs could loop forever re-visiting the same nodes back and forth.
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
order = [start]
for neighbor in graph[start]:
if neighbor not in visited:
order.extend(dfs(graph, neighbor, visited))
return orderDepth-first search goes as deep as possible down one path before backtracking to try another — the recursive call stack (from the recursion lesson) naturally provides the "remember where to backtrack to" behavior, the same way it did for tree traversal. The same visited set requirement applies here for the same reason: a graph's cycles mean the recursion could otherwise call itself into an infinite loop, re-visiting nodes it's already seen.
# Tree traversal — no visited tracking needed:
def tree_dfs(node):
if node is None:
return
process(node)
tree_dfs(node.left)
tree_dfs(node.right)
# Graph traversal — visited tracking is required:
def graph_dfs(graph, node, visited):
visited.add(node)
process(node)
for neighbor in graph[node]:
if neighbor not in visited:
graph_dfs(graph, neighbor, visited)A tree's "no cycles" guarantee means tree traversal never has to worry about revisiting a node — every node has exactly one path down to it from the root, so recursing into children can never loop back on itself. A graph has no such guarantee, so the visited set isn't an optional optimization, it's what makes graph traversal correct at all; skip it, and BFS/DFS on a graph with any cycle will genuinely never terminate.
Both are O(V + E) — every vertex and every edge gets visited at most once — so the choice between them is about what the traversal order actually needs to guarantee, not about performance.
Check your understanding
A quick comprehension check — not tracked, not graded, just for you.
1. What two restrictions does a tree have that a general graph doesn't?
2. Why is an adjacency list usually preferred over an adjacency matrix for a large, sparse graph?
3. Why does graph BFS/DFS require tracking visited nodes, while basic tree traversal doesn't need to?
4. Why is BFS specifically the right choice for finding the shortest path in an unweighted graph, rather than DFS?
Data structures & algorithms