Trees, Heaps, and Graphs: Traversal and Construction

DataData Structures as Behavioural Contracts covers what these structures promise and what that promise costs in Big-O terms. This page assumes that vocabulary and covers something it doesn't: the algorithms that actually walk, build, and maintain trees, heaps, and graphs, following the standard treatment in Cormen, Leiserson, Rivest, and Stein's algorithms textbook¹.

Tree Traversal

VisitingVisiting every node in a binary tree can be done in three distinct orders, each defined by when the current node is visited relative to its two children:

In-order traversal producing sorted output on a binary search tree isn't a coincidence — it's a direct consequence of the BST invariant (everything in a node's left subtree is smaller, everything in its right subtree is larger): visiting left, then the node, then right, at every level of the recursion, means smaller values are always fully explored before the current node is visited, and larger values always come after — the sortedness falls straight out of the invariant plus the visiting order, with no separate sorting step required.

Balancing a Binary Search Tree

TheThe in-order traversal above only gives O(log n) search, insert, and delete if the tree's height is O(log n) in the first place — and a plain binary search tree gives no guarantee of that at all. Insert already-sorted data (1, 2, 3, 4, 5, in that order) into a BST with no balancing and every new node becomes the right child of the last one, one after another:

insert(1) insert(2) insert(3) insert(4) insert(5), no rebalancing
1
 \
  2
   \
    3
     \
      4
       \
        5

That's a linked list wearing a tree's name — height n instead of log n, and every operation that relied on the tree's height being small degrades to O(n) along with it, silently, on exactly the input (already-sorted data) that a hand-built test fixture is likely to use without thinking twice about it. A self-balancing tree fixes this by restoring a height invariant after every insert or delete, rather than leaving height purely at the mercy of insertion order:

All three restore their invariant the same general way — a rotation, a local restructuring that changes which node is whose parent without disturbing the in-order sequence the tree represents — the difference between them is only how strict an invariant they insist on, and therefore how often a rotation is needed. That last row isn't a historical curiosity: it's the reason a relational database's index can look up one row among billions in a handful of disk reads rather than a handful of comparisons — the B-tree's branching factor is chosen specifically to make each node exactly one disk page, and the height that matters in practice is measured in disk reads, not element comparisons.

Heap Operations

WilliamsWilliams introduced the binary heap, packaged with the sift-up/sift-down operations below and heapsort as its direct application, as Algorithm 232 in a 1964 issue of Communications of the ACM — one of the earliest examples of a data structure being published, by name, as a reusable algorithmic tool rather than described only as part of solving one specific problem⁵. A binary heap keeps one invariant: every parent is smaller (a min-heap) or larger (a max-heap) than both its children — nothing is said about how siblings compare to each other, only parent-to-child. Stored compactly as an array (no pointers needed — a node at index i has children at 2i+1 and 2i+2), two operations maintain the invariant after it's disturbed:

Insert: add the new element at the end of the array, then sift up — repeatedly swap it with its parent while it's smaller (min-heap) than that parent, until the invariant holds again. Extract-min: remove the root (always the minimum in a min-heap, by the invariant), move the last element into the now-empty root position, then sift down — repeatedly swap it with whichever of its two children is smaller, until the invariant holds again. Both operations touch at most the height of the tree, which a balanced binary heap keeps at O(log n), giving O(log n) insert and extract — much better than the O(n) a naive "always keep the array sorted" approach would need for insertion.

Heapsort is a direct consequence of these two operations and nothing more: build a heap from all n elements (which can be done in O(n), faster than n individual inserts, by sifting down from the middle of the array outward), then repeatedly extract-min and place the result at the end of a growing sorted output — n extractions at O(log n) each gives O(n log n) overall, matching merge sort's bound but, unlike merge sort, using no extra memory beyond the array itself.

Graph Representations

AA graph can be stored as an adjacency matrix (an n×n grid, cell [i][j] marking whether an edge exists from i to j — O(1) to check any specific edge, but O(n²) space regardless of how many edges actually exist) or an adjacency list (each node keeps a list of just its own neighbours — O(V + E) space, proportional to what's actually there, at the cost of O(degree) rather than O(1) to check one specific edge). Real-world graphs are usually sparse (far fewer edges than the V² a dense graph would have), which is why adjacency lists are the default choice in practice.

Breadth-First Search versus Depth-First Search

BothBoth traverse every reachable node from a starting point, and differ only in which node they explore next — BFS uses a queue (explore all of the current node's neighbours before moving further out — level by level, like ripples spreading from a stone), DFS uses a stack, or equivalently, recursion (follow one path as far as it goes before backtracking).

On the graph above starting from A: BFS visits A, then B and C (both one step away), then D, E, and F (all two steps away) — order: A, B, C, D, E, F. DFS follows one branch to its end before backtracking: A, B, D, (backtrack) E, (backtrack) C, F.

The choice isn't arbitrary. BFS is the natural fit for shortest path in an unweighted graph, because it explores nodes in strict order of distance from the source — the first time it reaches any node is guaranteed to be via a shortest path, since every closer node was necessarily explored first. DFS is the natural fit for cycle detection and topological sorting (ordering nodes so every edge points from earlier to later in the order — only possible on a graph with no cycles at all), because its backtracking structure naturally reveals a "back edge" — an edge pointing to a node still on the current path, the direct signature of a cycle — and naturally produces a valid topological order by recording each node as finished exactly when there's nothing left to explore beneath it.

Graphs as a Model: State Machines and Control Flow

AA directed graph isn't only a data structure to store and search — it's also a way of modelling something else entirely, where the nodes and edges above stand for states and the transitions between them rather than for stored data at all. Two concrete cases already covered elsewhere on this site are both, underneath their own domain vocabulary, exactly the directed graph described above. A finite state machine is a directed graph where each node is a named state and each edge is a transition triggered by some event — game AI's classic FSM (patrol → alert → chase → attack → flee) is a small directed graph walked one edge at a time as events arrive, and its well-known failure mode — transitions multiplying combinatorially as designers add nuance — is exactly the cost of a dense graph growing dense on purpose. A control flow graph is the same structure applied to source code instead of behaviour: nodes are straight-line chunks of a function, edges are the possible jumps between them, and Code Path Analysis uses exactly that graph — traversed, not just stored — to derive a defensible minimum test suite from a function's own branching structure, via McCabe's cyclomatic complexity metric. Neither page needed to reinvent graph traversal to do this; both are BFS/DFS-style walks over a graph whose nodes and edges happen to mean something other than "data."

The balanced binary search tree covered here has one more augmentation worth knowing, beyond the plain structures above: store one extra summary value per node — the maximum reach of everything in that node's subtree — and the same tree can answer "which of these stored ranges overlap a given point" by ruling out whole subtrees cheaply, rather than checking every stored range individually. Interval Arithmetic covers that structure, an interval tree, in full.

References