Lexicographic Enumeration and Range Scans over a Trie

A comparison sort needs Θ(n log n) comparisons to order n keys, because it learns only one bit per comparison about the permutation. A trie has already spent the information before the sort would start: each key’s path spells its characters in order, and the children of a node are labelled by characters. Walking the structure in the right order therefore emits the keys sorted, with no comparisons between keys at all. The cost of that property is paid at build time in the node layout, and again at traversal time in the discipline the walker must keep.

The order is in the labels

Lexicographic order compares two strings at their first differing character; if one string is a prefix of the other, the shorter comes first. A trie encodes both rules structurally. Two keys diverge at the node where their paths separate, so the first differing character is the label of the two divergent edges, and visiting the smaller label first reproduces the comparison. The prefix case is handled by the terminal marker: a node that ends a key is emitted before descending into its children.

That gives the traversal rule directly. At each node, emit the key if the node is terminal, then visit children in increasing label order. A depth-first traversal obeying this rule visits keys in lexicographic order, and it does so in time proportional to the number of nodes visited, which for a full traversal is proportional to total key bytes.

The rule presupposes that children can be visited in label order. This is where the node layout from child representation in tries becomes a semantic choice rather than a performance one. A packed array with a bitmap holds children in increasing label order by construction, so ordered iteration is a scan with a popcount to recover labels. A sorted array of labels gives the same order after a binary search. A linked list in insertion order does not, and iterating it in label order requires sorting the node’s children first — an O(d log d) step per node, which destroys the linearity of the traversal. A hash map per node has the same problem, and its iteration order is not even stable across runs in most implementations. Any trie intended to serve ordered queries must keep its children ordered.

Emitting the key text

The traversal needs the key string as it descends, and there are two ways to produce it. The first keeps a buffer of the characters on the current path, appending on descent and truncating on ascent. The buffer holds at most the maximum key length, so its memory is bounded and allocated once. Copying into an output string at each terminal node costs the key length per emitted key, which is unavoidable if the caller wants a copy.

The second recovers the key from the node identity, which requires that the node know its parent and the label on the edge to it — feasible in a mutable pointer-based trie, and in a flat array layout only if parent pointers are stored explicitly, which doubles the array. The buffer approach is simpler and is what a recursive or explicit-stack traversal does naturally.

An explicit stack is worth preferring over recursion when keys can be long. Recursion depth equals key length, and a trie over long strings — file paths, for instance — can exceed a thread’s default stack. The explicit form stores the iterator state of each level, which is exactly the parent pointer, the next child index, and the buffer length.

struct Node {
    children: Vec<(u8, usize)>, // (label, index), sorted by label
    terminal: bool,
}

fn keys_in_order(nodes: &[Node]) -> Vec<Vec<u8>> {
    let mut out = Vec::new();
    let mut path = Vec::new();
    let mut stack: Vec<(usize, usize)> = vec![(0, 0)]; // (node, next child)

    while let Some(&(node, next)) = stack.last() {
        let n = &nodes[node];
        if next == 0 && n.terminal {
            out.push(path.clone());
        }
        if next < n.children.len() {
            let (label, child) = n.children[next];
            stack.last_mut().unwrap().1 += 1;
            path.push(label);
            stack.push((child, 0));
        } else {
            stack.pop();
            if !stack.is_empty() {
                path.pop();
            }
        }
    }
    out
}

The terminal emission is guarded by *next == 0 so that a node’s key is emitted exactly once, on first arrival, before its subtree. Without that guard, a node revisited after a child returns would emit its key again in the wrong position.

Range scans

A range query asks for all keys between two bounds. A B-tree answers it by seeking to the lower bound and walking leaves, and the cost is the logarithm of the key count plus the number of results. A trie answers it by descending along the lower bound to the point where the bound’s path ends, then enumerating in order from there until the upper bound is passed.

The mechanics of the first step: walk the lower bound’s characters. At each node, for each child label strictly less than the bound’s character, that entire subtree lies below the bound and is excluded; the child matching the character is followed. When the walk ends — either at a node that terminates the lower bound or at a missing edge — enumeration begins from the current position. The seek touches one node per character of the lower bound, and the work at each node (finding the child for the bound’s character) is bounded by the node’s degree, so the seek cost is bounded by key length times maximum degree rather than by the number of keys.

Stopping is the symmetric problem, and it is where naive implementations waste work. Enumerating the whole subtree below the lower bound and filtering results against the upper bound is correct but can traverse an arbitrarily large number of keys that will be discarded. The efficient version prunes: at each node during enumeration, compare the path so far against the upper bound’s prefix, and if the path is already lexicographically greater, skip the subtree. Since the traversal is in order, the first result exceeding the bound means the scan is finished, and the whole scan terminates rather than merely filtering.

The asymmetry between seek and stop is worth noting. A seek to a point in a trie is cheap because it is a single path. A scan between two points is cheap because the in-order traversal visits only keys in the interval, provided the pruning test is implemented. Neither property holds for an unordered hash structure, where a range query degenerates to a full scan, and neither holds for a trie with unordered children, where the seek cannot decide which subtrees to exclude.

Prefix counting without enumeration

A common query is “how many keys start with this prefix”, which the traversal above answers only by enumerating them. Storing a subtree count at each node turns it into a path walk: descend the prefix and read the count at the final node. The count costs one integer per node, which in a compact layout can be the largest field in the header, so it is not free.

An alternative avoids the per-node count entirely: store nothing extra and count by traversing the subtree below the prefix node, or store only a cheap subtree flag to skip empty subtrees quickly. The trade is exact. Per-node counts make counting O(prefix length) and make every insertion update every node on the path — O(key length) writes, which is the same order as the insertion itself, so the update cost is only a constant factor. Without counts, counting is O(size of matching subtree), which can be the whole trie.

The count also enables order-statistic queries: “the k-th key in sorted order” descends by comparing k against the cumulative child counts, one level at a time, in O(key length × degree) time. This is the trie analogue of selecting by rank in an order-statistic tree, and it is why tries with subtree counts are used as ordered indexes rather than plain sets.

The cache behaviour of ordered traversal

Ordered traversal is the operation where a trie’s memory layout shows most clearly, because it touches nodes in an order determined by the keys rather than by recent access. A pointer-based trie visits nodes scattered across the heap; the traversal follows the tree structure, so it touches each node once, and the miss rate per node is close to one for a trie too large for cache.

Two layout properties improve this, and both come from the node representation rather than the traversal algorithm. First, children stored inline rather than behind pointers keep the descent within one cache line per node. Second, allocating nodes in depth-first order during construction places sibling subtrees contiguously, so an in-order walk touches memory in near-sequential order — the same locality benefit that a depth-first-allocated B-tree obtains. Neither is required for correctness, and both change traversal cost by changing the number of cache misses per node.

The extreme case is a double-array trie, where all states live in one or two contiguous arrays and the traversal reads them in an order that is a permutation of the array. Locality is then a function of how construction assigned state numbers, and a build that assigns states in a depth-first pass over the key set produces near-sequential access.

Where enumeration stops being the right tool

Ordered traversal over a trie is linear in nodes visited, which for a full enumeration of keys with no shared prefixes is proportional to total key bytes. A B-tree enumeration is linear in the number of keys plus the tree height. When keys are long and share long prefixes, the trie visits every byte of every key plus every internal node, and the constant per node is a cache miss. For a dictionary of ten million keys of average length twelve with little prefix sharing, the trie holds on the order of a hundred million nodes and a full enumeration touches all of them; a B-tree touches ten million leaves. The trie wins on prefix-restricted queries and loses on full scans, and that difference is a property of the structure, not of the implementation.

Compression closes part of that gap by removing the single-child chains that dominate node counts, at the cost of making traversal do a string comparison per edge. The trade is developed in path compression and Patricia tries.