Trie

Trie (also known as a digital tree, radix tree, or prefix tree) is an ordered multi-way tree data structure within computation and algorithms used to store and query a dynamic set or associative map of strings over a finite alphabet Σ of size σ = |Σ|. First described mathematically by Axel Thue in 1912, applied to binary digital search by René de la Briandais in 1959, and named trie by Edward Fredkin in 1960 after the middle syllable of information retrieval (pronounced /ˈtriː/ by Fredkin and Knuth, though commonly pronounced /ˈtraɪ/ today to distinguish it from a general "tree"), a trie encodes keys implicitly by their root-to-node path rather than storing full keys inside tree nodes.

Whereas comparison-based search trees such as the AVL tree, red-black tree, and B-tree require Θ(log n) key comparisons—costing O(m log n) character comparisons when keys are strings of length m with shared prefixes—a trie inspects each symbol of a query string P = P[1..m] at most once, executing point lookup, insertion, deletion, and longest-prefix matching in worst-case O(m) time independent of the total number n of stored keys within computational complexity theory. Across networking, text indexing, and computational genomics, tries and their path-compressed variants underpin IP routing longest-prefix lookup tables, the Aho–Corasick multi-pattern string matcher, suffix trees and suffix arrays, and k-mer indexing in high-throughput DNA sequencing.

Formal Automaton Definition Over Alphabet Σ

Let Σ = {c₁, ..., c_σ} be an ordered alphabet of size σ = |Σ| and S = {W₁, ..., W_n} ⊆ Σ* a dictionary of n strings. The standard trie 𝒯(S) is the minimal tree-shaped deterministic finite-state automaton (DFA) accepting S:

1. Prefix-Node Bijection: Every node u ∈ 𝒯(S) corresponds to a distinct prefix pref(u) ∈ Σ* of some W_i ∈ S, with root r representing the empty string ε.
2. Symbol-Labeled Edges: Each edge (u, v) labeled a ∈ Σ transitions to pref(v) = pref(u) · a.
3. Terminal Marking: Each node u carries a boolean flag isWord(u) indicating whether pref(u) ∈ S (or strings end with a unique sentinel § ∉ Σ so all keys terminate at leaves).

Because keys sharing prefix P follow the same path to u_P, the subtree at u_P holds all keys in S beginning with P, and an alphabetical preorder traversal of 𝒯(S) emits S in lexicographical order (forming the basis of burstsort and MSD radix sort).

Node Representation Trade-offs: Direct Array vs. Ternary Search Trie

The time and memory efficiency of a trie depends on how each node u represents its outgoing transition function δ(u, ·) : Σ → V ∪ {NIL}:

Radix Trees and Donald Morrison's PATRICIA Trie (1968)

In an uncompressed trie storing long keys with sparse branching, a single unique suffix of length L generates a chain of L unary internal nodes (each having out-degree 1), inflating node count to O(∑ |W_i|). A radix tree (or compact prefix tree) eliminates all unary internal nodes by contracting every non-branching path into a single edge labeled with a substring slice (start, length). Because every remaining internal node has out-degree ≥ 2, a radix tree storing n distinct sentinel-terminated strings contains at most n − 1 internal nodes and n leaves, reducing total node count to O(n) regardless of key lengths.

Donald R. Morrison's PATRICIA (Practical Algorithm To Retrieve Information Coded in Alphanumeric, 1968) applies path compression over the binary alphabet Σ = {0, 1}: each internal node stores only the integer bit index b at which the two branching subtrees first differ, skipping intermediate bits during descent and performing a single full-key verification at the reached leaf.

Aho–Corasick Failure Links and Suffix Trees

Augmenting a trie of k pattern strings {P₁, ..., P_k} with failure links f(u)—pointing to the deepest trie node whose prefix pref(f(u)) is a proper suffix of pref(u)—yields the Aho–Corasick string-matching automaton (1975), which scans a text T of length N in linear O(N + ∑ |P_i| + z) time to report all z pattern occurrences simultaneously. Constructing a path-compressed trie of all N suffixes of a single text T[1..N]§ yields Weiner's (1973) and Ukkonen's (1995) linear-time suffix tree, whose lexicographical leaf order forms the suffix array and enables Burrows–Wheeler transform indexing. In lossless data compression, the prefix-free codebook tree built by Huffman coding is a binary trie in which all source symbols reside at the leaves.

In Internet backbone routers (BGP forwarding tables containing > 10⁶ CIDR prefixes), packet forwarding requires longest-prefix matching (LPM): finding the routing table entry whose variable-length subnet prefix shares the longest match with the packet's destination IP address. Hardware and kernel forwarding planes implement multi-bit stride tries (such as the Linux kernel LC-trie) that inspect 4 to 8 bits per step to resolve longest-prefix lookups in a few SRAM accesses. Over the four-nucleotide DNA alphabet Σ = {A, C, G, T} (σ = 4), 4-way nucleotide tries and compacted k-mer radix trees enable deterministic O(k) taxonomic read classification, single-cell barcode demultiplexing under bounded Hamming distance via A* search algorithm / branch-and-bound trie traversal, and spatial subdivision via multidimensional tries (quadtrees and octrees).

How does a trie compare to a hash table for string lookups?

Both a trie and a hash table inspect all m characters of a query string P[1..m] in O(m) time. However, a trie provides worst-case O(m) guarantees with zero hash collisions, supports prefix searches, autocomplete, longest-prefix matching, and lexicographical range iteration natively, and shares storage across common prefixes, whereas a hash table cannot answer prefix or ordered range queries without scanning all buckets.

What is the difference between a standard trie, a radix tree, and a suffix tree?

A standard trie stores a dictionary of strings with one node per prefix character; a radix tree compresses that trie by merging every non-branching single-child chain into a single multi-character edge; and a suffix tree is the radix tree constructed over all N suffixes T[i..N]§ of a single string T.

1. de la Briandais, R. (1959). "File searching using variable length keys." Proceedings of the Western Joint Computer Conference, 295–298. https://doi.org/10.1145/1457838.1457895
2. Fredkin, E. (1960). "Trie memory." Communications of the ACM, 3(9), 490–499. https://doi.org/10.1145/367390.367400
3. Morrison, D. R. (1968). "PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric." Journal of the ACM, 15(4), 514–534. https://doi.org/10.1145/321479.321481
4. Aho, A. V., & Corasick, M. J. (1975). "Efficient string matching: An aid to bibliographic search." Communications of the ACM, 18(6), 333–340. https://doi.org/10.1145/360825.360855
5. Bentley, J. L., & Sedgewick, R. (1997). "Fast algorithms for sorting and searching strings." Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 360–369. https://doi.org/10.5555/314161.314321