Tries

A trie (from retrieval, pronounced "try" or "tree") is a tree in which each edge is labeled with a single symbol from a fixed alphabet $\Sigma$, and each root-to-node path spells out a string — the concatenation of the edge labels along that path. A node is marked as terminal (or "is a word") if the string spelled out from the root to that node belongs to the stored set of keys. Crucially, a node can be both an internal branching point and terminal: the paths for `"car"` and `"card"` overlap entirely up through `car`, so the node reached by `c → a → r` is simultaneously the end of the key `"car"` and an ancestor of the node for `"card"`. This design enforces a powerful invariant: any two keys sharing a length-$k$ prefix follow identical paths for their first $k$ edges. The trie never stores that shared prefix twice. Contrast this with a hash table, where `"car"` and `"card"` hash to unrelated buckets with no structural relationship, or with a binary search tree, where the relationship between keys is by lexicographic comparison of whole strings, not by shared prefix structure. In a trie, the relationship is explicit and physical: it is literally a shared subpath. Because branching is driven by the alphabet rather than by comparisons, a node in a trie over an alphabet of size $|\Sigma|$ has up to $|\Sigma|$ children, one per possible next symbol. This is the key structural departure from binary trees (which always have at most two children regardless of the domain). The tradeoff is immediate: wider branching means shallower trees (depth equals key length $m$, not $\log n$), but each node potentially needs $|\Sigma|$ pointers, most of which may be null. This is the central space–time tradeoff that every trie implementation must confront, and it motivates variants discussed below (hashed children, compressed/radix tries, ternary search tries).

Node layout. Each trie node stores:

• an array (or map) `children[c]` for `c` in the alphabet, giving a pointer to the child reached by symbol `c`, or null/absent if no key uses that continuation;
• a boolean flag `isEnd`, true if the path from the root to this node spells a complete stored key.

The root represents the empty string and is never itself marked `isEnd` unless the empty string is a stored key.

Search(key). Walk from the root, consuming one character of `key` per step, following `children[key[i]]`. If at any point the required child is missing, the key is absent — return false immediately. If all characters are consumed successfully, the key is present if and only if the final node's `isEnd` flag is true (a path existing is not sufficient — `"car"` existing as a path does not mean `"car"` was inserted, if only `"card"` was ever inserted).

Insert(key). Walk from the root as in search, but whenever a required child is missing, create it. After consuming all characters, mark the final node's `isEnd` flag true.

Delete(key). Walk down to the node for `key` as in search; if the key is not present, do nothing. Otherwise unmark `isEnd`. Then, to reclaim space, walk back up from that node toward the root, deleting any node that has become both non-terminal and childless — but stop as soon as a node is found that is terminal or has another child, since removing further would destroy other stored keys.

Prefix query / autocomplete. Walk to the node for the prefix string (as in search, but without requiring `isEnd`); if that path exists, every key with this prefix corresponds to a terminal node reachable via DFS from that point. This is the operation that hash tables cannot do efficiently, since hashing destroys the ordering/prefix relationship between strings. ``` structure TrieNode: children: map from symbol to TrieNode // sparse; empty by default isEnd: boolean := false structure Trie: root := new TrieNode() function SEARCH(trie, key): // returns true iff key is stored node := trie.root for i := 0 to length(key) - 1: c := key[i] if c not in node.children: return false node := node.children[c] return node.isEnd function INSERT(trie, key): node := trie.root for i := 0 to length(key) - 1: c := key[i] if c not in node.children: node.children[c] := new TrieNode() node := node.children[c] node.isEnd := true function DELETE(trie, key): path := [trie.root] // record nodes visited, for cleanup node := trie.root for i := 0 to length(key) - 1: c := key[i] if c not in node.children: return // key not present; nothing to do node := node.children[c] path.append(node) if not node.isEnd: return // key not present as a full word node.isEnd := false // prune dead nodes bottom-up for i := length(path) - 1 downto 1: current := path[i] parent := path[i - 1] if current.isEnd or SIZE(current.children) > 0: break // still needed by some other key remove current from parent.children // safe to delete // (root is never deleted) function STARTS_WITH_PREFIX(trie, prefix): // does any stored key have this prefix? node := trie.root for i := 0 to length(prefix) - 1: c := prefix[i] if c not in node.children: return false node := node.children[c] return true // reachable, regardless of isEnd function COLLECT_ALL_WITH_PREFIX(trie, prefix): node := trie.root for i := 0 to length(prefix) - 1: c := prefix[i] if c not in node.children: return [] // no key extends this prefix node := node.children[c] results := [] DFS_COLLECT(node, prefix, results) return results function DFS_COLLECT(node, built, results): if node.isEnd: results.append(built) for (c, child) in node.children: DFS_COLLECT(child, built + c, results) ```

Time complexity. Let $m$ be the length of the key involved in an operation, $|\Sigma|$ the alphabet size, and $n$ the number of stored keys.

• `SEARCH`, `INSERT`, `DELETE` each perform exactly one pass over the $m$ characters of the key, doing $O(1)$ work per character (one array/map lookup, or one node creation) if children are stored in a direct-indexed array of size $|\Sigma|$. This gives $O(m)$ time, with no dependence on $n$ — the number of other keys stored does not appear anywhere in the loop bound.
• If children are stored in a hash map (common when $|\Sigma|$ is large or sparse, e.g. Unicode), each step costs $O(1)$ expected time, giving $O(m)$ expected time overall, or $O(m \log |\Sigma|)$ worst case if a balanced tree of children is used instead to avoid hash-collision attacks.
• `COLLECT_ALL_WITH_PREFIX` costs $O(p + z)$, where $p$ is the prefix length and $z$ is the total size (in characters) of all matching keys returned — you cannot avoid touching output you must produce.

This is a genuinely different complexity regime from a balanced binary search tree, which costs $O(m \log n)$ per operation ($\log n$ comparisons, each comparison costing up to $O(m)$ to compare two strings character by character in the worst case — so a naive BST on strings can cost $O(m \log n)$, and even a hash table costs $O(m)$ expected time just to hash the key, plus collision resolution). The trie's $O(m)$ bound holds deterministically (no probabilistic assumption about hash distribution) and is completely insensitive to $n$: a trie with a billion keys answers a query on a 5-character string exactly as fast as one with ten keys, provided the alphabet-indexed array lookup is $O(1)$.

Correctness — invariant argument. Define the path invariant: for every node $v$ reachable from the root by consuming symbols $s_1 s_2 \ldots s_k$, $v.isEnd$ is true if and only if the string $s_1 s_2 \ldots s_k$ is currently a member of the stored key set.

• `INSERT(key)` maintains the invariant by construction: it creates exactly the missing nodes along the path for `key`'s characters (leaving all other paths, hence all other keys' terminal flags, untouched), then sets `isEnd := true` only at the node for the full string `key`. No other node's flag is altered.
• `DELETE(key)` maintains the invariant symmetrically: it sets `isEnd := false` only at the node for `key` (only if it was previously true — a no-op is correct if `key` was absent), and the subsequent bottom-up pruning removes a node only if it is both non-terminal (`isEnd = false`, so no key ends exactly there) and childless (no key extends further through it), meaning it is not on the path to any remaining stored string. The loop halts at the first ancestor that is terminal or has another child, so it never deletes structure still needed by another key.
• `SEARCH(key)` reads the invariant directly: it returns exactly `isEnd` of the node reached by following `key`'s characters (or `false` if that path doesn't fully exist, which correctly signals `key` is absent since no complete path means no chance of it being a terminal node for `key`).

By induction over the sequence of insert/delete operations, the invariant holds after every operation, so `SEARCH` is always correct.

Space complexity. In the worst case, a trie with $n$ keys of average length $m$ over alphabet size $|\Sigma|$ uses $O(n \cdot m)$ nodes (no two keys can force more than $n \cdot m$ distinct root-to-leaf path segments), and each node costs $O(|\Sigma|)$ words if children are stored as a direct array. This gives a worst-case space bound of $O(n \cdot m \cdot |\Sigma|)$ words — the dominant practical cost, especially for large alphabets like Unicode (where $|\Sigma|$ can be tens of thousands). This is the central tradeoff: the trie buys alphabet-driven, length-only lookup time at the price of per-node overhead proportional to alphabet size. Real implementations mitigate this via:

• Hashed children (map instead of array): reduces per-node space to $O(\text{actual branching factor})$ at each node, at the cost of hash-table constant factors and losing the guarantee of worst-case $O(1)$ per step (becomes expected $O(1)$).
• Radix tries / Patricia tries: compress chains of single-child nodes into one edge labeled with a substring, collapsing long unbranching paths (e.g., a trie holding only `"international"` and `"internationally"` need not allocate 13 separate one-child nodes). This reduces node count to $O(n)$ regardless of key length, at the cost of more complex edge-splitting logic on insert.
• Ternary search tries: each node has only 3 children (less-than, equal, greater-than a pivot character), trading array density for a binary-search-tree-like layout per character — giving $O(\log |\Sigma|)$ per character instead of $O(1)$, but with much better space for sparse alphabets.

Insert the keys `at`, `as`, `ate`, `cat` (in that order) into an empty trie, alphabet $\{a, c, e, s, t\}$, then search for `at`, `a`, and `care`, then delete `ate`.

Trie now stores: `at`, `as`, `ate`, `cat`. Note the node reached by `a→t` is terminal (`"at"` is a key) and has a child `e` (leading to `"ate"`) — exactly the overlapping-terminal situation the invariant is designed to handle.

`SEARCH("at")`: root → `a` (exists) → `t` (exists) → end of string, check `isEnd` at this node → true (it was set in step 1). Returns found.

`SEARCH("a")`: root → `a` (exists) → end of string, check `isEnd` at node `a` → false (node `a` was never marked terminal; it is purely a branching point for `at`, `as`, `ate`). Returns not found — even though `"a"` is a valid prefix, it was never inserted as a key. This distinguishes "is a prefix of something" from "is a stored key."

`SEARCH("care")`: root → `c` (exists, from `"cat"`) → `a` (exists) → `r` — no child `r` exists under this `a` node (its only child is `t`). Return false immediately, without examining the rest of the string. This demonstrates the early-termination benefit: search cost is bounded by the matched prefix length, often less than $m$ on a failed search.

`DELETE("ate")`: walk the path `root, a, t, e` (recording it). The node `e` is terminal — set `isEnd := false`. Begin pruning upward: node `e` is now non-terminal and childless → delete it from node `t`'s children. Move to node `t`: is it terminal? Yes (`"at"` still ends here) → stop pruning. The trie now stores `at`, `as`, `cat` again, with the `e`-node reclaimed. Node `t` and its `isEnd` flag are untouched, correctly preserving `"at"`. This trace shows all three subtleties at once: a node can be both terminal and branching (`t` under `a`), a node can be a valid path but not a stored key (`a` alone), and deletion must stop pruning as soon as it hits a node still needed by another key.

The trie was independently introduced twice in the same year. René de la Briandais proposed a version for efficient file searching, and Edward Fredkin, working at MIT and Bolt Beranek and Newman, published the structure and coined the name "trie" (from retrieval), suggesting the word be pronounced "tree" — though common usage has largely settled on "try" to avoid confusion with the general term "tree." Fredkin's paper framed the trie explicitly as a tool for lookup in large symbol tables and dictionaries, anticipating exactly the string-processing and networking applications that would later dominate its use.

Networking: Internet routers must perform longest-prefix match against forwarding tables containing hundreds of thousands of IP prefixes, on every packet, at multi-gigabit line rates. Compressed binary tries (Patricia tries) and multi-bit trie variants are the workhorse structure for this, because the $O(m)$ bound (with $m$ the fixed 32- or 128-bit address length) guarantees predictable per-packet lookup cost regardless of table size.

Autocomplete and predictive text: Search engines, IDE code completion, and mobile keyboard prediction all use trie-like structures (often augmented with frequency counts or compressed as a DAWG — directed acyclic word graph) to serve "complete this prefix" queries instantly as a user types, one keystroke at a time.

Spell-checking and dictionary lookup: Storing an entire dictionary as a trie lets a spell-checker verify a word in time proportional to the word's own length, and lets it efficiently generate nearby valid words (for suggestions) by walking neighboring paths.

Compilers and interpreters: Symbol tables, keyword recognizers, and lexical analyzers frequently use trie-based dispatch to match the longest valid token prefix at each position in source code, since this is exactly the longest-prefix-match problem tries were designed for.

Bioinformatics: Suffix tries and suffix trees (a compressed relative) index genomic sequences to support fast substring and pattern-matching queries over massive strings, leveraging the same prefix-sharing principle at the level of suffixes rather than whole words.

:::faq[Can a trie store keys that are not strings, like sequences of integers or bits]? Yes — a trie only requires that keys be sequences over some fixed, ordered alphabet; the "characters" can be bits (giving a binary trie, useful for IP routing over 32- or 128-bit addresses), bytes, or any discrete symbol set. The structure and complexity analysis are identical: search/insert/delete cost O(m) where m is the sequence length, regardless of what the symbols represent semantically.

Ask the tutor: How does a radix (Patricia) trie modify the insert algorithm to split a compressed edge when a new key diverges partway through it?