Trie in Depth: Prefix Trees From First Principles to Radix Trees, Autocomplete and Longest-Prefix Match

The idea: the key is the path

A trie is a rooted tree in which each edge is labelled with one symbol of the alphabet. The root represents the empty string. The node reached by following edges c, a, r represents the string car. Nodes do not store their string; the string is implied by the path. Each node carries a terminal flag that says whether a stored key ends there, because a path can exist for a prefix (ca) that is not itself a key.

This structure gives three properties that matter. First, lookup cost depends on the length of the key, not on how many keys are stored: finding a 10-character word takes 10 steps whether the trie holds a hundred words or a hundred million. Second, all keys with a common prefix live in one subtree, so prefix queries are a walk to that subtree followed by a traversal of it. Third, visiting children in symbol order yields keys in sorted order.

Representing children: the decision that sets memory cost

The engineering is in how each node stores its children; that choice sets memory use and lookup speed.

The fixed-array layout is the textbook version. With 26 slots of 8-byte pointers, each node costs at least 208 bytes, and deep nodes in a word list usually have one child, so almost all of that is empty. A dictionary of a few hundred thousand English words produces on the order of a million nodes, which puts a 26-slot array trie in the hundreds of megabytes. The hash-map layout wastes less per slot but pays a per-map overhead that, in managed languages, can be larger than the array for nodes with one or two children. Measure with your runtime's allocator tools (in Python, tracemalloc) rather than trusting estimates.

Complete operations in code

The implementation below uses a dictionary per node for clarity. Each node also stores count, the number of words in its subtree, which makes prefix counting O(prefix length), and top, a small cached list of the highest-scoring words below it, which makes autocomplete O(prefix length) instead of a subtree traversal.

class Node:
    __slots__ = ("children", "terminal", "count", "top")

    def __init__(self):
        self.children = {}   # character -> Node
        self.terminal = False
        self.count = 0       # number of words in this subtree
        self.top = []        # cached (score, word) pairs for autocomplete


class Trie:
    def __init__(self, k=3):
        self.root = Node()
        self.k = k

    def _find(self, prefix):
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def insert(self, word, score=0):
        path, node = [self.root], self.root
        for ch in word:
            node = node.children.setdefault(ch, Node())
            path.append(node)
        if node.terminal:
            return False                      # duplicate: counts unchanged
        node.terminal = True
        for n in path:
            n.count += 1
            n.top.append((score, word))
            n.top.sort(key=lambda t: (-t[0], t[1]))
            del n.top[self.k:]
        return True

    def contains(self, word):
        node = self._find(word)
        return node is not None and node.terminal

    def count_prefix(self, prefix):
        node = self._find(prefix)
        return 0 if node is None else node.count

    def complete(self, prefix):
        node = self._find(prefix)
        return [] if node is None else [w for _, w in node.top]

    def iter_words(self, prefix):
        """All words under prefix, in lexicographic order, without recursion."""
        start = self._find(prefix)
        if start is None:
            return
        stack = [(start, prefix)]
        while stack:
            node, acc = stack.pop()
            if node.terminal:
                yield acc
            for ch in sorted(node.children, reverse=True):
                stack.append((node.children[ch], acc + ch))

    def longest_prefix(self, text):
        node, best = self.root, 0
        for i, ch in enumerate(text):
            node = node.children.get(ch)
            if node is None:
                break
            if node.terminal:
                best = i + 1
        return text[:best]

    def delete(self, word):
        path, node = [self.root], self.root
        for ch in word:
            node = node.children.get(ch)
            if node is None:
                return False
            path.append(node)
        if not node.terminal:
            return False
        node.terminal = False
        for n in path:
            n.count -= 1
        for i in range(len(word), 0, -1):     # prune empty nodes bottom-up
            if path[i].count == 0:
                del path[i - 1].children[word[i - 1]]
            else:
                break
        return True

Insertion returns early on duplicates so counts stay correct. Enumeration uses an explicit stack, because recursion over long keys such as URLs can exceed the recursion limit. Deletion prunes nodes whose subtree became empty, stopping at the first node that still holds other words; without pruning, a trie under churn grows forever. Note what deletion does not do: it leaves stale entries in the cached top lists. Production autocomplete tries are usually rebuilt offline and swapped in rather than patched.

Worked example

Insert six words with popularity scores and query the result. The outputs in the comments are what the code above returns.

t = Trie(k=3)
for word, score in [("car", 50), ("card", 30), ("care", 80),
                    ("cat", 70), ("do", 20), ("dog", 60)]:
    t.insert(word, score)

t.count_prefix("ca")          # 4
t.complete("ca")              # ['care', 'cat', 'car']
list(t.iter_words("car"))     # ['car', 'card', 'care']
t.longest_prefix("cards")     # 'card'
t.contains("ca")              # False: a path exists but no word ends there
t.delete("card")              # True; node 'd' under 'car' is pruned
t.count_prefix("car")         # 2

Trace the first query. Walking c then a reaches a node whose count is 4, because car, card, care and cat all pass through it. The autocomplete call reads that node's cached list: care (80), cat (70) and car (50) are the three best scores, and card (30) was pushed out when the list was capped at k=3. The longest-prefix query walks c, a, r, d, sees terminal nodes at car and card, fails to find s under card, and returns the last terminal seen. The query for ca shows why the terminal flag exists: the path is present, but no word ends there. Deleting card removes one node, since its subtree count drops to zero, and leaves car and care intact.

The whole structure is ten nodes including the root, against 20 characters of input. For keys with little shared prefix, a trie uses more memory than the strings themselves.

Radix trees: collapsing single-child chains

In most real key sets, long runs of nodes have exactly one child. A radix tree (also called a compact or Patricia trie) replaces each such chain with one edge labelled by a string. The word list romane, romanus, romulus needs a single edge rom from the root instead of three nodes. With every internal node except terminals having at least two children, a radix tree over n keys has at most about 2n nodes regardless of key length.

Insertion becomes slightly more involved: when a new key diverges part-way along an edge, the edge is split at the divergence point, creating a new internal node with two children. The Linux kernel's page cache long used a radix tree (now the XArray), and the IPv4 routing table uses a level-compressed trie called fib_trie.

The adaptive radix tree (ART), published by Leis and colleagues in 2013 and used for indexes in systems such as HyPer and DuckDB, goes further: each node picks one of four layouts holding up to 4, 16, 48 or 256 children and grows or shrinks between them, getting array-speed lookups near the root without array-sized waste at the leaves.

Static tries: when the dictionary is built once

Many dictionaries change rarely: a tokenizer vocabulary, a search engine's term list, a list of blocked domains. For those, pointer-based nodes are the wrong trade. A double-array trie (Aoe, 1989) encodes the whole structure in two integer arrays, base and check: the child of state s on symbol c is at index base[s] + c, valid only if check at that index equals s. Lookups are two array reads per character, and the arrays can be memory-mapped from disk.

A finite state transducer (FST) goes beyond a trie by sharing suffixes as well as prefixes, so it becomes a minimal acyclic automaton rather than a tree, and it can attach outputs such as term IDs or file offsets to paths. Apache Lucene stores its term dictionary index this way. The common pattern is to build a mutable trie offline, freeze it into a compact static form, and ship it as an immutable artefact.

Where tries appear in systems and ML pipelines

• Longest-prefix match routing. A router must pick the most specific route that covers a destination address. A binary trie over address bits answers that in at most 32 steps for IPv4 or 128 for IPv6, and compressed variants cut the depth further.
• Tokenization. WordPiece-style tokenizers repeatedly take the longest vocabulary entry that matches at the current position, which is exactly longest_prefix above. The 2021 Fast WordPiece work by Song and colleagues builds a trie with failure links, borrowing the idea behind Aho-Corasick, to make this linear in input length.
• Constrained generation. When a language model must output one of a fixed set of strings, such as entity names or document IDs, a trie over the token sequences of the allowed outputs tells the decoder, at each step, which next tokens keep the output valid. The GENRE entity retrieval system (De Cao and colleagues, 2021) used this prefix-tree constraint during beam search.
• Multi-pattern search. Adding failure links to a trie of patterns gives Aho-Corasick, which finds every occurrence of every pattern in one pass; for a single pattern, see the KMP algorithm, whose failure function is the one-pattern special case.

Failure modes

• Memory blow-up. Array-per-node tries over large alphabets, or tries over keys with little shared prefix, can use many times the size of the raw keys. Measure bytes per key on real data before committing.
• Text encoding. Decide whether edges are bytes, Unicode code points or grapheme clusters, and normalise first. The string café can be written with a precomposed é or with e plus a combining accent; without normalisation (for example NFC) the two spellings sit on different paths. Case folding has the same problem.
• Unpruned deletes and stale caches. Deleting by clearing the terminal flag leaks nodes; cached aggregates drift unless rebuilt. Compute each node's list with a top-k pass in an offline build and swap the finished trie in atomically.
• Concurrency. A mutable trie shared between threads needs locking or copy-on-write. The simplest safe pattern for read-heavy workloads is an immutable snapshot replaced atomically when a new build is ready.

Choosing between a trie and the alternatives

For a static set, a sorted array finds a whole prefix range with two binary searches. A trie wins when you also need longest-prefix match, per-prefix aggregates, incremental updates, or matching character by character as input arrives.

What to do next

1. Write down the queries you need: exact, prefix range, prefix count, longest-prefix, or fuzzy. If it is only exact lookup, use a hash table.
2. Run the code above on a sample of your real keys and measure nodes, bytes per key and lookup time.
3. Decide the edge unit (bytes, code points) and a normalisation and case-folding rule before building anything.
4. Replace single-child chains with a radix tree once node count is the bottleneck; consider ART for binary keys.
5. If the key set changes rarely, freeze it into a double-array trie or FST and memory-map it.
6. Use iterative traversal, prune on delete, and rebuild cached aggregates rather than patching them.