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.

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.

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