Trees & Graphs: Walking Through Networks

What you'll learn

• What trees and graphs are, and why so much of computing is secretly one of them
• Tree vocabulary, binary search trees and the four classic traversals
• How to store a graph: adjacency list vs adjacency matrix
• DFS and BFS: how each works, when to pick which, and why you must remember what you visited
• How a grid is just a graph, how BFS finds the fewest steps, and how to count connected components
• You will write: a maze solver, a component counter and a binary search tree

The family tree and the subway map

A family tree has one ancestor at the top. Everyone has parents above and maybe children below, and you never loop back to yourself. That is a tree: a hierarchy. Folders on your computer, the HTML of a web page and a company's org chart are trees too.

A subway map is different. Stations are connected in every direction, you can ride in circles, and there is no "top". That is a graph: things (stations) and the links between them (tracks). Friends on a social network, cities and roads, web pages and links, tasks that depend on other tasks: all graphs.

Two big ideas for this lesson. First, a tree is a special graph: connected, with no cycles. Second, almost every "how do I get from here to there?" or "what is connected to this?" question is answered by walking the graph in one of two ways: depth-first (go as deep as you can, then back up) or breadth-first (explore everything close first, then farther out).

Trees and binary search trees

Vocabulary. A tree has a root (the top node). Each node has a parent (except the root) and zero or more children. A node with no children is a leaf. The depth of a node is how many edges separate it from the root. The height of the tree is the longest root-to-leaf path. (Some books count that path in edges, others in nodes. In this lesson's lab, height counts nodes, so a single node has height 1 and an empty tree has height 0.)

Binary tree: every node has at most two children, called left and right.

Binary search tree (BST): a binary tree with an ordering rule at every node: all keys in the left subtree are smaller, all keys in the right subtree are larger. Search and insert follow one path from the root, turning left or right, so they cost O(height).

• If the tree stays balanced, height is about log₂ n, so operations are O(log n).
• If you insert already-sorted keys 1, 2, 3, ... into a plain BST, every key goes to the right: the tree degenerates into a linked list of height n and operations become O(n). Self-balancing trees (AVL, red-black) fix this, and they are what TreeMap in Java and std::map in C++ use.

The four traversals. A traversal visits every node exactly once. With recursion each is three lines:

def inorder(node):            # left, node, right
    if node is None:
        return
    inorder(node.left)
    print(node.key)
    inorder(node.right)

def height(node):             # nodes on the longest path down
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

• Pre-order (node, left, right): copy a tree, print a folder before its contents.
• In-order (left, node, right): on a BST this visits keys in sorted order. This is the link between trees and sorting.
• Post-order (left, right, node): children before the parent, for example to add up folder sizes or delete a tree.
• Level-order (row by row from the top): it is the BFS you will meet in a minute, using a queue.

Graphs and how to store them

A graph is a set of vertices (nodes) and edges (links). Edges can be undirected (friendship) or directed (a one-way street, "follows", "depends on"), and may carry a weight (distance, cost). Two vertices are neighbours when an edge joins them. A cycle is a path that returns to where it started.

Adjacency list: for each vertex, a list of its neighbours.

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A"],
    "D": ["B"],
}

Memory O(V + E) and visiting all neighbours of a vertex costs exactly its degree. This is the default choice.

Adjacency matrix: a V x V table where m[u][v] says whether the edge exists. Memory O(V²), but "is there an edge u-v?" is O(1). It only pays off for small or very dense graphs. A graph with 100,000 vertices and 200,000 edges would need 10¹⁰ cells as a matrix but only about 400,000 list entries.

A grid is a graph without anyone drawing it. Every cell is a vertex; its neighbours are the cells up, down, left and right (stay inside the board, skip walls). You never store the edges, you compute them on the fly:

for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
    nr, nc = r + dr, c + dc
    if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != "#":
        ...   # (nr, nc) is a neighbour of (r, c)

DFS and BFS

Both visit every vertex reachable from a start vertex, in O(V + E) time. The only difference is the container that holds "vertices still to visit".

Depth-first search (DFS): a stack (or recursion, which is the call stack). Take a neighbour, then a neighbour of that neighbour, and so on until you are stuck, then back up. Like exploring a maze by always taking the next corridor and backtracking at dead ends.

Breadth-first search (BFS): a queue. Visit the start, then all its neighbours, then all of their new neighbours. It spreads like a ripple in a pond, one layer at a time.

from collections import deque

def bfs(graph, start):
    dist = {start: 0}                 # also serves as the "visited" set
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nxt in graph[node]:
            if nxt not in dist:       # never queue a vertex twice
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return dist                       # fewest edges from start to every reachable vertex

Replace popleft() by pop() on a list used as a stack and you have DFS (mark visited when you take a vertex off the stack, or when you push it, but be consistent).

Always remember what you visited. Graphs have cycles, so without a visited set the walk goes A, B, A, B ... forever. (A tree has no cycles and needs none; the only way "back" is the parent.) Mark a vertex when you enqueue it in BFS, otherwise it can be queued many times.

Which to use?

• BFS gives the fewest edges from the start to every other vertex when all steps cost the same. The queue processes vertices in order of distance: all at distance 1, then all at 2, and so on. That is why BFS solves "minimum moves in a maze". (With different edge weights you need Dijkstra, a later topic.)
• DFS is the natural fit for "explore everything", detecting cycles, ordering tasks by dependency and trying all options (backtracking). It uses memory proportional to the depth. With recursion, very deep graphs can overflow the call stack (Python stops at about 1,000 nested calls by default): use an explicit stack.

Connected components. In an undirected graph a component is a group of vertices that can all reach each other. To count them: loop over all vertices; whenever one is not visited yet, you found a new component, so add 1 and run a DFS or BFS from it to mark its whole group. Isolated vertices count as components of size 1.

Summary

• A tree is a connected graph without cycles; a BST keeps smaller keys left and larger keys right, so operations cost O(height): O(log n) balanced, O(n) when degenerate. In-order traversal of a BST gives sorted keys.
• A graph is vertices plus edges. Store it as an adjacency list (O(V + E) memory) unless it is small or dense. A grid is an implicit graph: compute neighbours on the fly.
• DFS (stack or recursion) goes deep; BFS (queue) goes layer by layer and finds the fewest edges when all steps cost the same. Both run in O(V + E).
• Always track visited vertices in a graph, and mark them when you enqueue them. Use an explicit stack for very deep graphs.
• Connected components: start a traversal from every unvisited vertex and count how many times you start.

Practice next: count the islands in a grid of land and water, check whether a graph has a cycle, and compute the level-order traversal of a binary tree with a queue. Then continue with Recursion & Dynamic Programming, and later Shortest Paths & Union-Find, which extends BFS to weighted graphs.