Tries in Depth
Why this exists
A hash set answers one question superbly: "is this exact string in the set?" It cannot answer the questions people actually type into a search box. "Which stored words start with inter?" "How many of them?" "What are the five most popular?" "What is the longest stored prefix of this address?" A hash of inter tells you nothing about the hash of internet; hashing deliberately destroys the shared structure between keys. Sorting keeps that structure (all words with a given prefix sit in one contiguous block) but every probe still compares whole strings.
A trie (also called a prefix tree or digital tree) keeps the structure and makes it the data structure itself. Every node stands for a prefix; every edge is one symbol; the root is the empty string. Two keys that share a prefix share the path for that prefix. Looking up a key of length follows edges, regardless of how many keys are stored. A million-word dictionary and a ten-word dictionary cost the same steps to probe. That independence from is the property that makes tries the right tool for prefix queries, autocomplete, spell checking, routing tables and a surprising family of bitwise problems.
The idea is older than most of computer science's vocabulary. René de la Briandais described storing words letter by letter in a tree in 1959 ("File searching using variable length keys"), and Edward Fredkin named it in 1960 in "Trie Memory" (CACM 3(9)), taking the word from retrieval. Fredkin pronounced it "tree"; nearly everyone now says "try" to avoid the obvious confusion. Donald Morrison's 1968 PATRICIA ("Practical Algorithm To Retrieve Information Coded in Alphanumeric", JACM 15(4)) compressed the single-child chains away, and that compressed form is what runs inside Berkeley-derived IP routing tables, Redis Streams and Ethereum's state database. Bentley and Sedgewick's 1997 ternary search tree made tries memory-friendly for large alphabets.
The short Tries section of the Trees overview introduced the basic insert and search. This lesson goes much deeper: three node representations and their memory costs, deletion with pruning, prefix counting, autocomplete with precomputed top-k, the trie-plus-backtracking pattern behind Word Search II, the XOR trie with a proof of why its greedy bit choice is optimal, offline query tricks, compressed (radix/Patricia) tries, ternary search trees and minimal automata, and where each of these runs in production.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "starts with", "prefix", "autocomplete", "type-ahead", "suggestions as the user types" | A trie; walk the prefix once, answer from the node you land on |
| "count how many words have prefix p" | Trie with a pass-through counter on every node |
| "find all dictionary words in this grid / board" | Trie of the dictionary + DFS backtracking that walks the trie in lockstep (Word Search II) |
| "replace each word by its shortest root", "longest stored prefix of x" | Walk the trie along x, remember the last end-of-word node (longest-prefix match) |
| "maximum XOR of two numbers", "max XOR with a query value" | Binary (XOR) trie over the bits, most significant first, greedy opposite bit |
| "max XOR with an element ≤ m" for many queries | Offline: sort queries by m, insert numbers in increasing order, then query the XOR trie |
| "count pairs with XOR < k" or "in [lo, hi]" | XOR trie with subtree counts; walk bits of k |
"wildcard . matches any letter" | Trie + DFS that branches at wildcards |
| "stream of characters, does any suffix form a word?" | Trie of reversed words, walk backwards from the newest character |
| "routing table", "IP prefix", "CIDR" | Longest-prefix match on a binary (radix) trie |
| Many keys share long prefixes, memory matters | Compressed trie (radix tree / Patricia) |
| Large alphabet (Unicode, bytes) and sparse children | Hash-map children, sorted-array children, or a ternary search tree |
| "exact match only", no prefix questions | A hash set is simpler and usually faster; a trie is overkill |
The core trigger is a question about prefixes of the keys (or prefixes of the bit strings of numbers). If every question is about whole keys, reach for a hash table; if questions are about order or ranges of whole keys, reach for a sorted structure. If they are about shared beginnings, reach for a trie.
Intuition & first principles
Picture a paper dictionary's thumb index. You open to the c section, then within it to ca, then car. Each step narrows the candidate set to the words sharing a longer beginning, and the step costs the same no matter how thick the dictionary is. A trie is that thumb index taken to its limit: one level of indexing per character.
Precisely: a trie over an alphabet storing a set of strings is a rooted tree in which
- every edge is labelled with one symbol of , and the edges leaving any node have distinct labels;
- the node reached from the root by following edges labelled represents the string ;
- a node exists if and only if the string it represents is a prefix of at least one string in ;
- each node carries a flag (or counter) saying whether the string it represents is itself in .
Property 3 is what makes it a trie rather than any tree of characters: the set of nodes is exactly the set of prefixes of , the prefix closure. Property 4 is needed because a key can be a proper prefix of another key: car and cart both live on the same path, and only the flag distinguishes "car was inserted" from "car is merely on the way to cart".
With those two properties, every operation is a walk:
- search(w): walk the symbols of ; fail if an edge is missing; at the end, return the node's flag.
- startsWith(p): walk ; succeed if every edge exists. The flag does not matter.
- insert(w): walk , creating any missing node on the way; set the flag at the end.
The cost of each is one step per symbol of the argument. The number of stored keys appears nowhere. What does appear is the cost of one step, which depends on how a node finds its child for a given symbol. That is the first design decision, and it dominates both speed and memory.
Three ways to store children
Array of slots. For lowercase English, children[26], indexed by ch - 'a'. A step is one array index: the fastest possible. The cost is memory: every node pays for 26 pointers whether it uses one or none. On a 64-bit machine that is bytes of pointers per node before the flag and allocator overhead. Deep in a dictionary trie most nodes have exactly one child, so roughly 25 of the 26 slots are null. With 32-bit indices into a node pool instead of pointers, the array shrinks to 104 bytes, which is the standard competitive-programming trick.
Hash map from symbol to child. Memory proportional to the actual number of children, any alphabet (Unicode, bytes, tokens), expected per step. The constant is much worse than an array index — hashing, probing, and a map header of tens of bytes per node even when empty. This is the natural choice in Python and JavaScript, and the right one when is large or unknown.
Sorted array (or list) of (symbol, child) pairs. Memory proportional to the number of children with almost no overhead; a step is a binary search () or, for the typical 1–3 children, a linear scan that fits in one cache line. Children come out in sorted order for free, which makes lexicographic enumeration trivial. Insertion costs to shift elements, which is irrelevant for read-mostly dictionaries. Production radix trees, including Redis's rax, use variations of this.
There are hybrids. The adaptive radix tree (ART, Leis, Kemper and Neumann, ICDE 2013) switches each node among four layouts (4, 16, 48 and 256 children) as it fills, getting array-speed lookups with sorted-array memory. Double-array tries (Aoe, 1989) pack all nodes into two integer arrays for compact static dictionaries.
flowchart LR
subgraph ARR["Array of 26"]
A0["node: a..z slots<br/>only 'a' and 'o' used<br/>24 null pointers"]
end
subgraph MAP["Hash map"]
M0["node: map a -> n1, o -> n2<br/>map header + 2 entries"]
end
subgraph SRT["Sorted pairs"]
S0["node: [(a, n1), (o, n2)]<br/>binary search or scan"]
end
ARR -->|"fastest step, most memory"| MAP
MAP -->|"any alphabet, expected O(1)"| SRT
| Representation | Step cost | Memory per node | Ordered iteration | Best for |
|---|---|---|---|---|
| Array of | , one index | pointers | Yes, by index | Small fixed alphabet, speed critical, contests |
| Hash map | Expected , larger constant | + map overhead | No (unless you sort) | Unicode, unknown alphabets, Python/JS |
| Sorted pairs | or tiny linear scan | , minimal overhead | Yes | Read-mostly dictionaries, memory-tight systems |
| Adaptive (ART) | for large nodes, scan for small | Grows with fill: 4/16/48/256 | Yes | Database indexes in memory |
Counting instead of flagging
Replace the boolean flag with two integers per node:
end: how many times exactly this string was inserted (supports multisets and duplicate inserts);pass: how many inserted strings pass through or end at this node.
pass at the node for prefix is the number of stored words with prefix , so countPrefix(p) is a walk plus a read. It also makes deletion easy, because a node whose pass falls to zero is no longer a prefix of anything and can be cut away. The root's pass is the total number of words.
Mechanics
The structure after four inserts
Insert car, cat, cart, dog into an empty trie. The diagram shows the result; * marks end-of-word nodes.
flowchart TD
R(("root")) -->|"c"| C["c"]
R -->|"d"| D["d"]
C -->|"a"| CA["ca"]
CA -->|"r"| CAR["car *"]
CA -->|"t"| CAT["cat *"]
CAR -->|"t"| CART["cart *"]
D -->|"o"| DO["do"]
DO -->|"g"| DOG["dog *"]
Note what is shared: car, cat and cart reuse the path c → a; cart reuses the whole of car. Thirteen symbols of input (3 + 3 + 4 + 3) produced only 9 nodes, root included; without sharing they would need 14. The saving grows with the amount of shared prefix in the data, which for natural language, URLs, file paths and IP addresses is large.
Trace: insert car, cat, cart, dog, then search "ca"
This is the same run the visualizer above plays, generated by scripts/traces/trie_insert.py. "New" means a node was allocated; "follow" means the edge already existed.
| Step | Operation | Symbol | From node | Action | Nodes (incl. root) | Words |
|---|---|---|---|---|---|---|
| 1 | insert car | c | root | new c | 2 | 0 |
| 2 | insert car | a | c | new ca | 3 | 0 |
| 3 | insert car | r | ca | new car, mark end | 4 | 1 |
| 4 | insert cat | c | root | follow | 4 | 1 |
| 5 | insert cat | a | c | follow | 4 | 1 |
| 6 | insert cat | t | ca | new cat, mark end | 5 | 2 |
| 7 | insert cart | c | root | follow | 5 | 2 |
| 8 | insert cart | a | c | follow | 5 | 2 |
| 9 | insert cart | r | ca | follow | 5 | 2 |
| 10 | insert cart | t | car | new cart, mark end | 6 | 3 |
| 11 | insert dog | d | root | new d | 7 | 3 |
| 12 | insert dog | o | d | new do | 8 | 3 |
| 13 | insert dog | g | do | new dog, mark end | 9 | 4 |
| 14 | search ca | c | root | follow | 9 | 4 |
| 15 | search ca | a | c | follow, reach ca | 9 | 4 |
| 16 | search ca | — | ca | ca is not end-of-word: search = False, startsWith = True | 9 | 4 |
Two things to read off the trace. First, the 13 insertion steps did 13 symbol steps — exactly the total input length, with no dependence on how many words were already present. Second, step 16 is the distinction that catches people: the walk for ca succeeds, so ca is a prefix of stored words, but no one inserted ca itself.
Deletion with pruning
Deleting w must undo exactly what inserting w did, and must not damage other words sharing its path. With pass counters the rule is mechanical:
- Check
search(w); if false, there is nothing to delete. - Walk
wfrom the root, decrementingpasson every node along the path (root included). - If some child's
passreaches 0, no other word uses that child or anything below it. Cut the edge to it and stop: the entire dead chain is garbage. - If you reach the end node without cutting, decrement its
end.
The recursive textbook version (recurse to the end, unset the flag, and on the way back delete any child that has no children and no flag) does the same thing without counters. Both are .
Continuing the example: delete car. Every node on the path still has pass ≥ 1 afterwards (cart still passes through car), so nothing is cut; only end of car drops to 0. Then delete cart: at node car, pass falls from 1 to 0, so the edge ca → r is removed, freeing both car and cart. Seven nodes remain: root, c, ca, cat, d, do, dog.
flowchart TD
R(("root pass=2")) -->|"c"| C["c pass=1"]
R -->|"d"| D["d pass=1"]
C -->|"a"| CA["ca pass=1"]
CA -.->|"r cut: pass hit 0"| CAR["car (freed)"]
CA -->|"t"| CAT["cat * pass=1"]
CAR -.-> CART["cart (freed)"]
D -->|"o"| DO["do pass=1"]
DO -->|"g"| DOG["dog * pass=1"]
Longest-prefix match
"Given a string , which stored key is the longest prefix of ?" Walk through the trie and remember the last node with end > 0 you passed. Stop at the first missing edge or at the end of . The remembered node is the answer. This is the replace words problem (replace each word in a sentence by its shortest stored root — remember the first end node instead of the last) and, with bits instead of characters, the IP forwarding problem: a router stores prefixes like 10.0.0.0/8 and 10.1.0.0/16 and must forward each packet using the longest one that matches the destination address. The network layer lesson works through the forwarding rule; the trie is the software data structure that implements it.
Autocomplete: top-k per node
Autocomplete asks: given prefix , return the highest-scoring stored strings that start with . Three designs, with very different cost profiles:
- DFS at query time. Walk to the node for , then explore its subtree, collecting all words and selecting the top with a heap. Cost: where is the size of the subtree. For a one-letter prefix in a million-word dictionary, is a large fraction of the trie. Fine for small dictionaries; unacceptable for a search box that fires on every keystroke.
- Lexicographic order shortcut. If the score is lexicographic order (as in LeetCode's Search Suggestions System), a DFS that visits children in alphabetical order can stop after words. Cost . This only works for that one scoring rule.
- Precomputed top-k at every node. Each node stores the list of the best words in its subtree. Query: walk , return the list. , independent of subtree size. Insert of a word with score walks its path and offers the word to each node's list (insert in sorted position, drop the -th): per insert.
The third design is what production autocomplete services resemble: precompute aggressively, keep query time tiny. The cost is memory: references per node. For nodes that is extra references; with and pointers of 8 bytes, 80 extra bytes per node — comparable to the node itself. Common mitigations: store top-k only at nodes up to some depth (short prefixes are the expensive ones; deep prefixes have small subtrees and DFS is cheap there), store integer word IDs instead of strings, or store only at branching nodes of a compressed trie. Score updates (a query becomes popular) are the hard part: increasing a score is easy (re-offer along the path), but decreasing one may evict a word from a list that then needs a replacement from deeper down, which is why real systems typically rebuild these tables in batch and serve a static snapshot.
Word Search II: trie + backtracking
Given a grid of letters and a list of words, find all words that can be traced through adjacent cells without reusing a cell. Searching each word separately repeats the same DFS prefixes over and over. Instead, insert every word into a trie and run one DFS from each cell, walking the trie in lockstep with the grid: moving to a neighbouring cell with letter is allowed only if the current trie node has a child . The trie prunes every path that is not a prefix of some word, which is most of them.
Two refinements make it fast in practice:
- store the complete word at its end node (instead of a flag) so you never rebuild strings during DFS, and clear it once found to avoid duplicates;
- prune the trie as you go: after returning from a child, if that child now has no children and no word, delete it. Once every word through a branch has been found, the DFS stops exploring that branch entirely.
Worst-case cost is still exponential in word length (roughly paths for maximum word length ), but the trie bounds the explored paths by the prefixes actually present in the dictionary, which is what makes it pass. The backtracking lesson covers the mark/unmark discipline on the grid.
The XOR trie
Treat each non-negative integer as a fixed-width bit string, most significant bit first — say 31 bits for values below . Insert the numbers into a binary trie (two children per node: bit 0 and bit 1). To find the stored number maximizing , walk from the root and at each bit position (from high to low) prefer the child whose bit is the opposite of bit of ; take the same-bit child only when the opposite one does not exist. Each step where you got the opposite bit sets bit of the result.
flowchart TD
R(("root")) -->|"bit4 = 0"| Z["0xxxx: 3, 10, 5, 2, 8"]
R -->|"bit4 = 1"| O["1xxxx: 25"]
Z -->|"bit3 = 0"| ZZ["00xxx: 3, 5, 2"]
Z -->|"bit3 = 1"| ZO["01xxx: 10, 8"]
O -->|"bit3 = 1"| OO["11xxx: 25"]
Q["query x = 5 = 00101"] -.->|"want bit4 = 1"| O
Why "maximum XOR of a pair" becomes easy: insert every number, query every number, take the maximum. for bits, against for checking all pairs. The one-pass variant queries each number against those inserted before it and then inserts it, which also handles the "pairs " phrasing.
Trace on nums = [3, 10, 5, 25, 2, 8] with bits. First the per-bit walk for the query against the full set:
| Bit | Bit of | Wanted | Child taken | Candidates left | Result so far |
|---|---|---|---|---|---|
| 4 | 0 | 1 | 1 (exists) | {25} | 10000 |
| 3 | 0 | 1 | 1 (exists) | {25} | 11000 |
| 2 | 1 | 0 | 0 (exists) | {25} | 11100 |
| 1 | 0 | 1 | 0 (forced) | {25} | 11100 |
| 0 | 1 | 0 | 1 (forced) | {25} | 11100 |
Result . Then the one-pass scan (query against earlier numbers, then insert):
| Index | x | Best partner among earlier | Best XOR for this x | Overall best |
|---|---|---|---|---|
| 0 | 3 | — (trie empty) | — | — |
| 1 | 10 | 3 | 9 | 9 |
| 2 | 5 | 10 | 15 | 15 |
| 3 | 25 | 5 | 28 | 28 |
| 4 | 2 | 25 | 27 | 28 |
| 5 | 8 | 25 | 17 | 28 |
The maximum pair XOR is 28, matching a brute-force check of all 15 pairs.
The ladder: brute force → better → optimal
The running problem: store words of average length and answer queries of the form "how many stored words start with ?" ().
Rung 1: scan every word
For each query, loop over all words and test word.startswith(p). Each test is in the worst case, so a query is and the whole job . No preprocessing, no extra memory. With words and queries this is character comparisons — far too slow.
Rung 2: a hash map of every prefix
Preprocess: for each word, insert every one of its prefixes into a hash map counting occurrences. A query is one hash lookup of : to hash it. Preprocessing costs time and memory, because a word of length has prefixes of average length that must each be hashed and stored as separate strings. For short words this is genuinely competitive. For long keys (URLs of 100+ characters, file paths) the quadratic memory hurts, and it cannot enumerate the words, only count them.
Rung 3: sort + binary search
Sort the words. All words with prefix form one contiguous block, from the first word to the first word followed by a character larger than any symbol (in practice, p with its last character incremented, or p + ''). Two binary searches give the block: per query, preprocessing, and no extra memory beyond the sorted array. It also enumerates the matching words (they are the block) and supports top-k by lexicographic order trivially. This is a seriously good solution and is what many real systems do with a static sorted file (see the indexing deep dive — a B-tree prefix scan is this idea on disk). Its weakness is updates: inserting into a sorted array is .
Rung 4: trie
Build a trie with pass counters: time and at most nodes. A query walks edges and reads one counter: , independent of . Insertions and deletions are . It also supports enumeration (DFS below the node), top-k (precomputed lists), longest-prefix match and wildcard search, none of which the hash map can do and some of which the sorted array does less naturally.
| Rung | Preprocess | Query | Insert/delete | Extra memory | Enumerate matches |
|---|---|---|---|---|---|
| Scan all words | none | / | none | Yes, slowly | |
| Hash map of prefixes | expected | characters | No | ||
| Sorted array + binary search | none | Yes, contiguous block | |||
| Trie with counters | nodes node size | Yes, subtree DFS |
The trie wins on asymptotics; the sorted array often wins on memory and cache behaviour for static data. Know both and say so in an interview.
Correctness
The trie invariant
Let be the multiset of strings currently stored. The invariant after every operation:
(I1) For every string , a node representing exists if and only if is a prefix of at least one string in (or is empty). (I2) That node's
passequals the number of strings in having as a prefix, and itsendequals the multiplicity of in .
Initially , only the root exists (representing the empty string), pass = end = 0. Both hold.
Insert . The walk visits exactly the nodes representing the prefixes for , creating those that are missing. After the insert, the new has as new prefixes exactly the prefixes of , all of which now exist; no other node was created, so (I1) holds. Each prefix of gains exactly one string with that prefix, and the walk increments pass on exactly those nodes; end of 's node increments by one. Every other node's counts are unchanged, as are the true counts. (I2) holds.
Delete (with ). The walk decrements pass on the nodes for prefixes of — exactly the prefixes whose count drops by one in . If at prefix the counter reaches 0, then by (I2) no string of has prefix , hence none has any extension of as a prefix either; by (I1) the nodes for and everything below it must not exist, and cutting the edge removes exactly that subtree. If no counter reaches 0, the final node remains and its end drops by one. Both invariants hold for .
Queries. By (I1), the walk for succeeds iff is a prefix of some stored string, so startsWith is correct. By (I2), the node's pass is the count of words with prefix and its end > 0 iff , so countPrefix and search are correct.
Why the greedy XOR walk is optimal
Claim. For a fixed and a set of -bit numbers, the walk that at each bit position from down to takes the child with bit opposite to 's whenever it exists returns .
Key fact. For any bit position , . So if two numbers agree on all bits above and differ at bit , the one with a 1 at bit is larger, no matter what the lower bits are.
Proof by induction on the bit position. Let be the set of candidates still consistent with the path after deciding bits ; the invariant is that contains some maximizer of over , and that all produce the same high bits of (positions above ), namely the high bits of the optimum. Initially ; it trivially holds. At bit :
- If some has bit opposite to 's, those make bit of equal to 1. Every with the same bit as makes it 0, and by the key fact is strictly worse than every opposite-bit candidate (they tie above ). So every maximizer in has the opposite bit; restricting to the opposite child keeps a maximizer.
- If no has the opposite bit, all have bit of equal to 0 and the restriction to the same-bit child removes nothing.
Either way the invariant holds for . After bit 0 the remaining candidates all equal some maximizer's value of .
The same argument explains why the bits must be inserted most significant first: the greedy decision is only safe when no later decision can outweigh it, which is true from the top down and false from the bottom up. It also shows why every number must be padded to the same width : comparing a 3-bit number against a 31-bit number bit-by-bit from different depths would compare bits of different weights.
Complexity
Let be the length of the key in the operation, the number of stored keys, the total stored length, the alphabet size, the number of nodes.
| Operation | Array children | Hash-map children | Sorted children |
|---|---|---|---|
| insert, search, startsWith, countPrefix | expected | (insert: worst) | |
| delete with pruning | expected | worst | |
| enumerate the words under a prefix | |||
| autocomplete with stored top-k | query, insert | same | same |
| XOR trie query/insert ( bits) | — | — | |
| Space | with big constant |
Best case for search is (first symbol has no edge); worst case is . Nothing is amortized except the hash-map resizing inside each node.
Space, concretely. is the worst case (no shared prefixes). Natural data shares a lot; the trace above stored 13 symbols in 9 nodes. The node size is the real issue. A C++ array-of-26 node with 8-byte pointers and two int counters is bytes; a million nodes is 216 MB. The same million nodes as hash-map nodes in CPython cost several hundred bytes each (a dict alone is around 64 bytes empty and grows from there, plus the object header), so Python tries of tens of millions of characters run out of memory long before they run out of time. Index-based pools (int children into one big array) halve the pointer cost and remove per-node allocation.
Cache behaviour. A trie walk is a chain of dependent loads — pointer chasing — and each node is likely in a different cache line. A lookup of a 10-character key can cost 10 cache misses, about a microsecond if the trie does not fit in cache. A hash set lookup of the same key costs one hash computation and typically one or two misses. This is why hash sets beat tries for exact lookups in practice even though both are "", and why compressed tries and ART, which cut the number of nodes on a path, matter so much for performance.
Implementation
The canonical implementation: a counting trie with insert, search, startsWith, countPrefix and delete with pruning. Python and TypeScript use hash-map children (any alphabet); Java and C++ use an array of 26 for lowercase ASCII. All four run the same tests on car, cat, cart, dog.
class TrieNode:
__slots__ = ("children", "end", "pass_count")
def __init__(self) -> None:
self.children: dict[str, "TrieNode"] = {}
self.end = 0 # how many times this exact word was inserted
self.pass_count = 0 # how many inserted words pass through this node
class Trie:
def __init__(self) -> None:
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
node.pass_count += 1
for ch in word:
nxt = node.children.get(ch)
if nxt is None:
nxt = node.children[ch] = TrieNode()
node = nxt
node.pass_count += 1
node.end += 1
def _walk(self, s: str) -> TrieNode | None:
node = self.root
for ch in s:
node = node.children.get(ch)
if node is None:
return None
return node
def search(self, word: str) -> bool:
node = self._walk(word)
return node is not None and node.end > 0
def starts_with(self, prefix: str) -> bool:
return self._walk(prefix) is not None
def count_prefix(self, prefix: str) -> int:
node = self._walk(prefix)
return 0 if node is None else node.pass_count
def delete(self, word: str) -> bool:
if not self.search(word):
return False
node = self.root
node.pass_count -= 1
for ch in word:
child = node.children[ch]
child.pass_count -= 1
if child.pass_count == 0: # nobody else uses this branch
del node.children[ch] # prune the whole dead chain
return True
node = child
node.end -= 1
return True
def node_count(self) -> int:
stack, count = [self.root], 0
while stack:
node = stack.pop()
count += 1
stack.extend(node.children.values())
return count
if __name__ == "__main__":
t = Trie()
for w in ["car", "cat", "cart", "dog"]:
t.insert(w)
assert t.node_count() == 9
assert not t.search("ca") and t.starts_with("ca")
assert t.search("car") and t.search("cart") and not t.search("cars")
assert t.count_prefix("ca") == 3 and t.count_prefix("car") == 2
assert t.count_prefix("") == 4 and t.count_prefix("x") == 0
assert t.delete("car") and not t.search("car") and t.search("cart")
assert t.count_prefix("car") == 1 and t.node_count() == 9
assert t.delete("cart") and not t.starts_with("car") and t.starts_with("ca")
assert t.node_count() == 7
assert not t.delete("zzz") and not t.delete("car")
assert t.count_prefix("") == 2
print("trie ok")
public class Trie {
static final class Node {
final Node[] next = new Node[26];
int end; // times this exact word was inserted
int pass; // words passing through this node
}
private final Node root = new Node();
public void insert(String word) {
Node node = root;
node.pass++;
for (int i = 0; i < word.length(); i++) {
int c = word.charAt(i) - 'a';
if (node.next[c] == null) node.next[c] = new Node();
node = node.next[c];
node.pass++;
}
node.end++;
}
private Node walk(String s) {
Node node = root;
for (int i = 0; i < s.length() && node != null; i++) {
node = node.next[s.charAt(i) - 'a'];
}
return node;
}
public boolean search(String word) {
Node n = walk(word);
return n != null && n.end > 0;
}
public boolean startsWith(String prefix) {
return walk(prefix) != null;
}
public int countPrefix(String prefix) {
Node n = walk(prefix);
return n == null ? 0 : n.pass;
}
public boolean delete(String word) {
if (!search(word)) return false;
Node node = root;
node.pass--;
for (int i = 0; i < word.length(); i++) {
int c = word.charAt(i) - 'a';
Node child = node.next[c];
child.pass--;
if (child.pass == 0) { // prune the dead branch
node.next[c] = null;
return true;
}
node = child;
}
node.end--;
return true;
}
public int nodeCount() {
return count(root);
}
private int count(Node n) {
int total = 1;
for (Node ch : n.next) if (ch != null) total += count(ch);
return total;
}
private static void check(boolean cond, String msg) {
if (!cond) throw new AssertionError(msg);
}
public static void main(String[] args) {
Trie t = new Trie();
for (String w : new String[] {"car", "cat", "cart", "dog"}) t.insert(w);
check(t.nodeCount() == 9, "nodes");
check(!t.search("ca") && t.startsWith("ca"), "ca");
check(t.search("car") && t.search("cart") && !t.search("cars"), "search");
check(t.countPrefix("ca") == 3 && t.countPrefix("car") == 2, "count");
check(t.countPrefix("") == 4 && t.countPrefix("x") == 0, "count2");
check(t.delete("car") && !t.search("car") && t.search("cart"), "del car");
check(t.countPrefix("car") == 1 && t.nodeCount() == 9, "after car");
check(t.delete("cart") && !t.startsWith("car") && t.startsWith("ca"), "del cart");
check(t.nodeCount() == 7, "pruned");
check(!t.delete("zzz") && !t.delete("car"), "missing");
check(t.countPrefix("") == 2, "total");
System.out.println("trie ok");
}
}
#include <array>
#include <cassert>
#include <iostream>
#include <memory>
#include <string>
class Trie {
struct Node {
std::array<std::unique_ptr<Node>, 26> next{};
int end = 0; // times this exact word was inserted
int pass = 0; // words passing through this node
};
Node root;
const Node* walk(const std::string& s) const {
const Node* node = &root;
for (char ch : s) {
node = node->next[ch - 'a'].get();
if (!node) return nullptr;
}
return node;
}
static int count(const Node* n) {
int total = 1;
for (const auto& ch : n->next)
if (ch) total += count(ch.get());
return total;
}
public:
void insert(const std::string& word) {
Node* node = &root;
node->pass++;
for (char ch : word) {
auto& slot = node->next[ch - 'a'];
if (!slot) slot = std::make_unique<Node>();
node = slot.get();
node->pass++;
}
node->end++;
}
bool search(const std::string& word) const {
const Node* n = walk(word);
return n && n->end > 0;
}
bool startsWith(const std::string& prefix) const { return walk(prefix) != nullptr; }
int countPrefix(const std::string& prefix) const {
const Node* n = walk(prefix);
return n ? n->pass : 0;
}
bool erase(const std::string& word) {
if (!search(word)) return false;
Node* node = &root;
node->pass--;
for (char ch : word) {
auto& slot = node->next[ch - 'a'];
slot->pass--;
if (slot->pass == 0) { // prune: unique_ptr frees the whole chain
slot.reset();
return true;
}
node = slot.get();
}
node->end--;
return true;
}
int nodeCount() const { return count(&root); }
};
int main() {
Trie t;
for (const char* w : {"car", "cat", "cart", "dog"}) t.insert(w);
assert(t.nodeCount() == 9);
assert(!t.search("ca") && t.startsWith("ca"));
assert(t.search("car") && t.search("cart") && !t.search("cars"));
assert(t.countPrefix("ca") == 3 && t.countPrefix("car") == 2);
assert(t.countPrefix("") == 4 && t.countPrefix("x") == 0);
assert(t.erase("car") && !t.search("car") && t.search("cart"));
assert(t.countPrefix("car") == 1 && t.nodeCount() == 9);
assert(t.erase("cart") && !t.startsWith("car") && t.startsWith("ca"));
assert(t.nodeCount() == 7);
assert(!t.erase("zzz") && !t.erase("car"));
assert(t.countPrefix("") == 2);
std::cout << "trie ok\n";
return 0;
}
class TrieNode {
children: Map<string, TrieNode> = new Map();
end = 0; // times this exact word was inserted
pass = 0; // words passing through this node
}
class Trie {
root = new TrieNode();
insert(word: string): void {
let node = this.root;
node.pass++;
for (const ch of word) {
let nxt = node.children.get(ch);
if (!nxt) {
nxt = new TrieNode();
node.children.set(ch, nxt);
}
node = nxt;
node.pass++;
}
node.end++;
}
private walk(s: string): TrieNode | undefined {
let node: TrieNode | undefined = this.root;
for (const ch of s) {
node = node.children.get(ch);
if (!node) return undefined;
}
return node;
}
search(word: string): boolean {
const n = this.walk(word);
return n !== undefined && n.end > 0;
}
startsWith(prefix: string): boolean {
return this.walk(prefix) !== undefined;
}
countPrefix(prefix: string): number {
return this.walk(prefix)?.pass ?? 0;
}
delete(word: string): boolean {
if (!this.search(word)) return false;
let node = this.root;
node.pass--;
for (const ch of word) {
const child = node.children.get(ch)!;
child.pass--;
if (child.pass === 0) {
node.children.delete(ch); // prune the dead branch
return true;
}
node = child;
}
node.end--;
return true;
}
nodeCount(): number {
const stack: TrieNode[] = [this.root];
let count = 0;
while (stack.length) {
const n = stack.pop()!;
count++;
for (const c of n.children.values()) stack.push(c);
}
return count;
}
}
function check(cond: boolean, msg: string): void {
if (!cond) throw new Error(msg);
}
const t = new Trie();
for (const w of ["car", "cat", "cart", "dog"]) t.insert(w);
check(t.nodeCount() === 9, "nodes");
check(!t.search("ca") && t.startsWith("ca"), "ca");
check(t.search("car") && t.search("cart") && !t.search("cars"), "search");
check(t.countPrefix("ca") === 3 && t.countPrefix("car") === 2, "count");
check(t.countPrefix("") === 4 && t.countPrefix("x") === 0, "count2");
check(t.delete("car") && !t.search("car") && t.search("cart"), "del car");
check(t.countPrefix("car") === 1 && t.nodeCount() === 9, "after car");
check(t.delete("cart") && !t.startsWith("car") && t.startsWith("ca"), "del cart");
check(t.nodeCount() === 7, "pruned");
check(!t.delete("zzz") && !t.delete("car"), "missing");
check(t.countPrefix("") === 2, "total");
console.log("trie ok");
A few deliberate choices. delete checks search first, so it never decrements counters for a word that is not there — the most common deletion bug. The pruning step cuts the first node whose counter reaches zero, which removes the whole chain below it in one assignment; there is no need to walk to the end. The C++ version relies on unique_ptr to free the chain recursively, which is fine for word-length depths but would overflow the stack for keys of millions of symbols (use an explicit stack or a node pool there).
The XOR trie
Maximum XOR of any two numbers in an array, values in . The node pool is two parallel integer arrays (child[node][bit]), sized for the worst case of nodes. Every version also checks itself against brute force.
B = 31 # values are in [0, 2**31)
class XorTrie:
def __init__(self) -> None:
self.child = [[0, 0]] # node 0 is the root; 0 also means "no child"
def insert(self, x: int) -> None:
node = 0
for b in range(B - 1, -1, -1):
bit = (x >> b) & 1
if self.child[node][bit] == 0:
self.child[node][bit] = len(self.child)
self.child.append([0, 0])
node = self.child[node][bit]
def max_xor(self, x: int) -> int:
node, result = 0, 0
for b in range(B - 1, -1, -1):
bit = (x >> b) & 1
want = bit ^ 1
if self.child[node][want]:
result |= 1 << b
node = self.child[node][want]
else:
node = self.child[node][bit]
return result
def find_maximum_xor(nums: list[int]) -> int:
trie = XorTrie()
best = 0
for i, x in enumerate(nums):
if i:
best = max(best, trie.max_xor(x))
trie.insert(x)
return best
def brute(nums: list[int]) -> int:
return max((a ^ b for a in nums for b in nums), default=0)
if __name__ == "__main__":
assert find_maximum_xor([3, 10, 5, 25, 2, 8]) == 28
assert find_maximum_xor([14, 70, 53, 83, 49, 91, 36, 80, 92, 51, 66, 70]) == 127
assert find_maximum_xor([0]) == 0
assert find_maximum_xor([2**31 - 1, 0]) == 2**31 - 1
seed, data = 12345, []
for _ in range(200):
seed = (seed * 1103515245 + 12345) % (2**31)
data.append(seed)
assert find_maximum_xor(data) == brute(data)
print("xor trie ok")
public class XorTrie {
static final int B = 31;
private final int[][] child;
private int size = 1; // node 0 is the root; 0 also means "no child"
XorTrie(int maxInserts) {
child = new int[maxInserts * B + 1][2];
}
void insert(int x) {
int node = 0;
for (int b = B - 1; b >= 0; b--) {
int bit = (x >> b) & 1;
if (child[node][bit] == 0) child[node][bit] = size++;
node = child[node][bit];
}
}
int maxXor(int x) {
int node = 0, result = 0;
for (int b = B - 1; b >= 0; b--) {
int bit = (x >> b) & 1, want = bit ^ 1;
if (child[node][want] != 0) {
result |= 1 << b;
node = child[node][want];
} else {
node = child[node][bit];
}
}
return result;
}
static int findMaximumXor(int[] nums) {
XorTrie trie = new XorTrie(nums.length);
int best = 0;
for (int i = 0; i < nums.length; i++) {
if (i > 0) best = Math.max(best, trie.maxXor(nums[i]));
trie.insert(nums[i]);
}
return best;
}
static int brute(int[] nums) {
int best = 0;
for (int a : nums) for (int b : nums) best = Math.max(best, a ^ b);
return best;
}
private static void check(boolean cond, String msg) {
if (!cond) throw new AssertionError(msg);
}
public static void main(String[] args) {
check(findMaximumXor(new int[] {3, 10, 5, 25, 2, 8}) == 28, "ex1");
check(findMaximumXor(new int[] {14, 70, 53, 83, 49, 91, 36, 80, 92, 51, 66, 70}) == 127, "ex2");
check(findMaximumXor(new int[] {0}) == 0, "single");
check(findMaximumXor(new int[] {Integer.MAX_VALUE, 0}) == Integer.MAX_VALUE, "max");
long seed = 12345;
int[] data = new int[200];
for (int i = 0; i < 200; i++) {
seed = (seed * 1103515245L + 12345L) % (1L << 31);
data[i] = (int) seed;
}
check(findMaximumXor(data) == brute(data), "random");
System.out.println("xor trie ok");
}
}
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <vector>
constexpr int B = 31;
class XorTrie {
std::vector<std::array<int, 2>> child{{0, 0}}; // node 0 = root, 0 = no child
public:
void insert(int x) {
int node = 0;
for (int b = B - 1; b >= 0; --b) {
int bit = (x >> b) & 1;
if (child[node][bit] == 0) {
child[node][bit] = static_cast<int>(child.size());
child.push_back({0, 0});
}
node = child[node][bit];
}
}
int maxXor(int x) const {
int node = 0, result = 0;
for (int b = B - 1; b >= 0; --b) {
int bit = (x >> b) & 1, want = bit ^ 1;
if (child[node][want]) {
result |= 1 << b;
node = child[node][want];
} else {
node = child[node][bit];
}
}
return result;
}
};
int findMaximumXor(const std::vector<int>& nums) {
XorTrie trie;
int best = 0;
for (std::size_t i = 0; i < nums.size(); ++i) {
if (i) best = std::max(best, trie.maxXor(nums[i]));
trie.insert(nums[i]);
}
return best;
}
int brute(const std::vector<int>& nums) {
int best = 0;
for (int a : nums)
for (int b : nums) best = std::max(best, a ^ b);
return best;
}
int main() {
assert(findMaximumXor({3, 10, 5, 25, 2, 8}) == 28);
assert(findMaximumXor({14, 70, 53, 83, 49, 91, 36, 80, 92, 51, 66, 70}) == 127);
assert(findMaximumXor({0}) == 0);
assert(findMaximumXor({2147483647, 0}) == 2147483647);
std::int64_t seed = 12345;
std::vector<int> data;
for (int i = 0; i < 200; ++i) {
seed = (seed * 1103515245LL + 12345LL) % (1LL << 31);
data.push_back(static_cast<int>(seed));
}
assert(findMaximumXor(data) == brute(data));
std::cout << "xor trie ok\n";
return 0;
}
const B = 31;
class XorTrie {
// child[2 * node + bit]; node 0 is the root, 0 also means "no child"
child: number[] = [0, 0];
insert(x: number): void {
let node = 0;
for (let b = B - 1; b >= 0; b--) {
const bit = (x >>> b) & 1;
if (this.child[2 * node + bit] === 0) {
this.child[2 * node + bit] = this.child.length / 2;
this.child.push(0, 0);
}
node = this.child[2 * node + bit];
}
}
maxXor(x: number): number {
let node = 0;
let result = 0;
for (let b = B - 1; b >= 0; b--) {
const bit = (x >>> b) & 1;
const want = bit ^ 1;
if (this.child[2 * node + want] !== 0) {
result += 2 ** b; // avoid sign issues of |= at bit 31
node = this.child[2 * node + want];
} else {
node = this.child[2 * node + bit];
}
}
return result;
}
}
function findMaximumXor(nums: number[]): number {
const trie = new XorTrie();
let best = 0;
nums.forEach((x, i) => {
if (i > 0) best = Math.max(best, trie.maxXor(x));
trie.insert(x);
});
return best;
}
function brute(nums: number[]): number {
let best = 0;
for (const a of nums) for (const b of nums) best = Math.max(best, (a ^ b) >>> 0);
return best;
}
function check(cond: boolean, msg: string): void {
if (!cond) throw new Error(msg);
}
check(findMaximumXor([3, 10, 5, 25, 2, 8]) === 28, "ex1");
check(findMaximumXor([14, 70, 53, 83, 49, 91, 36, 80, 92, 51, 66, 70]) === 127, "ex2");
check(findMaximumXor([0]) === 0, "single");
check(findMaximumXor([2147483647, 0]) === 2147483647, "max");
let seed = 12345n;
const data: number[] = [];
for (let i = 0; i < 200; i++) {
seed = (seed * 1103515245n + 12345n) % 2147483648n;
data.push(Number(seed));
}
check(findMaximumXor(data) === brute(data), "random");
console.log("xor trie ok");
Variant: autocomplete with top-k per node
Each node keeps the best (score, word) pairs in its subtree, sorted by descending score and then alphabetically. Inserting offers the word to every node on its path. The query is a walk plus a copy.
import bisect
class ACNode:
__slots__ = ("children", "top")
def __init__(self) -> None:
self.children: dict[str, "ACNode"] = {}
self.top: list[tuple[int, str]] = [] # (-score, word), ascending = best first
class Autocomplete:
def __init__(self, k: int) -> None:
self.k = k
self.root = ACNode()
def _offer(self, node: ACNode, key: tuple[int, str]) -> None:
if key in node.top:
return
bisect.insort(node.top, key)
if len(node.top) > self.k:
node.top.pop() # drop the (k+1)-th best
def add(self, word: str, score: int) -> None:
key = (-score, word)
node = self.root
self._offer(node, key)
for ch in word:
node = node.children.setdefault(ch, ACNode())
self._offer(node, key)
def suggest(self, prefix: str) -> list[str]:
node = self.root
for ch in prefix:
node = node.children.get(ch)
if node is None:
return []
return [w for _, w in node.top]
# Search Suggestions System style: equal scores, so ties break alphabetically.
ac = Autocomplete(3)
for p in ["mobile", "mouse", "moneypot", "monitor", "mousepad"]:
ac.add(p, 0)
assert [ac.suggest("mouse"[:i]) for i in range(1, 6)] == [
["mobile", "moneypot", "monitor"],
["mobile", "moneypot", "monitor"],
["mouse", "mousepad"],
["mouse", "mousepad"],
["mouse", "mousepad"],
]
# Weighted: popularity beats alphabet.
ac2 = Autocomplete(2)
for w, s in [("car", 5), ("cart", 9), ("cat", 7), ("dog", 1)]:
ac2.add(w, s)
assert ac2.suggest("ca") == ["cart", "cat"]
assert ac2.suggest("car") == ["cart", "car"]
assert ac2.suggest("z") == []
print("autocomplete ok")
This version assumes each word is added once with its final score. Supporting score changes requires removing the old (score, word) pair from every list on the path and, if a list shrinks below , refilling it from the children's lists — the reason production systems rebuild offline.
Variant: Word Search II
def find_words(board: list[list[str]], words: list[str]) -> list[str]:
root: dict = {}
for w in words:
node = root
for ch in w:
node = node.setdefault(ch, {})
node["$"] = w # store the whole word at its end
rows, cols = len(board), len(board[0])
found: list[str] = []
def dfs(r: int, c: int, parent: dict) -> None:
ch = board[r][c]
node = parent[ch]
word = node.pop("$", None)
if word is not None: # pop: report each word once
found.append(word)
board[r][c] = "#" # mark visited
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] in node:
dfs(nr, nc, node)
board[r][c] = ch # unmark
if not node: # prune exhausted branch
parent.pop(ch)
for r in range(rows):
for c in range(cols):
if board[r][c] in root:
dfs(r, c, root)
return found
board = [list("oaan"), list("etae"), list("ihkr"), list("iflv")]
assert sorted(find_words(board, ["oath", "pea", "eat", "rain"])) == ["eat", "oath"]
assert find_words([list("ab"), list("cd")], ["abcb"]) == []
assert sorted(find_words([list("ab"), list("cd")], ["ab", "abdc", "ca", "x"])) == ["ab", "abdc", "ca"]
print("word search II ok")
Using plain dicts as nodes with the reserved key "$" is a common Python idiom: a node is just its children map. The pruning line if not node: parent.pop(ch) is the difference between passing and timing out on adversarial inputs such as a board of all a and words a, aa, aaa, ….
Variant: replace words (shortest root)
def replace_words(roots: list[str], sentence: str) -> str:
trie: dict = {}
for r in roots:
node = trie
for ch in r:
node = node.setdefault(ch, {})
node["$"] = True
def shortest_root(word: str) -> str:
node = trie
for i, ch in enumerate(word):
if ch not in node:
return word
node = node[ch]
if "$" in node:
return word[: i + 1] # first end node = shortest root
return word
return " ".join(shortest_root(w) for w in sentence.split())
assert replace_words(["cat", "bat", "rat"], "the cattle was rattled by the battery") == "the cat was rat by the bat"
assert replace_words(["a", "b", "c"], "aadsfasf absbs bbab cadsfafs") == "a a b c"
assert replace_words(["ab", "abc"], "abcd ab a") == "ab ab a"
print("replace words ok")
Changing return word[: i + 1] from "first end node" to "last end node seen" turns this into longest-prefix match — the routing-table rule.
Variant: maximum XOR with an element no larger than m (offline)
Each query asks for over stored . Answering online needs a trie whose nodes store the minimum value in their subtree (and skip children whose minimum exceeds ). The offline trick is simpler: sort the queries by , sort the numbers, and insert numbers into the trie only once they become eligible. When a query is answered, the trie contains exactly the numbers .
def maximize_xor(nums: list[int], queries: list[list[int]]) -> list[int]:
B = 30 # values < 2**30 in this problem
child = [[0, 0]]
def insert(x: int) -> None:
node = 0
for b in range(B - 1, -1, -1):
bit = (x >> b) & 1
if not child[node][bit]:
child[node][bit] = len(child)
child.append([0, 0])
node = child[node][bit]
def best(x: int) -> int:
node, res = 0, 0
for b in range(B - 1, -1, -1):
bit = (x >> b) & 1
if child[node][bit ^ 1]:
res |= 1 << b
node = child[node][bit ^ 1]
else:
node = child[node][bit]
return res
nums = sorted(nums)
order = sorted(range(len(queries)), key=lambda i: queries[i][1])
ans = [-1] * len(queries)
j = 0
for qi in order:
x, m = queries[qi]
while j < len(nums) and nums[j] <= m:
insert(nums[j])
j += 1
if j: # at least one eligible number
ans[qi] = best(x)
return ans
assert maximize_xor([0, 1, 2, 3, 4], [[3, 1], [1, 3], [5, 6]]) == [3, 3, 7]
assert maximize_xor([5, 2, 4, 6, 6, 3], [[12, 4], [8, 1], [6, 3]]) == [15, -1, 5]
print("offline max xor ok")
Cost: . The general lesson — when queries carry a threshold, sort them by it and grow the structure monotonically — recurs with Fenwick trees, segment trees and union-find.
Variant: a compressed (radix) trie
Edges carry strings instead of single characters, and no non-root node that is not an end-of-word has exactly one child. Insertion splits an edge at the first mismatch.
class RadixNode:
__slots__ = ("edges", "end")
def __init__(self) -> None:
self.edges: dict[str, tuple[str, "RadixNode"]] = {} # first char -> (label, child)
self.end = False
def common_prefix_len(a: str, b: str) -> int:
i = 0
while i < len(a) and i < len(b) and a[i] == b[i]:
i += 1
return i
class RadixTree:
def __init__(self) -> None:
self.root = RadixNode()
def insert(self, word: str) -> None:
node = self.root
while word:
first = word[0]
if first not in node.edges:
leaf = RadixNode()
leaf.end = True
node.edges[first] = (word, leaf)
return
label, child = node.edges[first]
k = common_prefix_len(label, word)
if k < len(label): # split the edge at k
mid = RadixNode()
mid.edges[label[k]] = (label[k:], child)
node.edges[first] = (label[:k], mid)
child = mid
node, word = child, word[k:]
node.end = True
def search(self, word: str) -> bool:
node = self.root
while word:
edge = node.edges.get(word[0])
if edge is None or not word.startswith(edge[0]):
return False
node, word = edge[1], word[len(edge[0]):]
return node.end
def node_count(self) -> int:
stack, count = [self.root], 0
while stack:
n = stack.pop()
count += 1
stack.extend(child for _, child in n.edges.values())
return count
rt = RadixTree()
for w in ["car", "cat", "cart", "dog"]:
rt.insert(w)
assert rt.search("car") and rt.search("cart") and rt.search("cat") and rt.search("dog")
assert not rt.search("ca") and not rt.search("do") and not rt.search("carts")
assert rt.node_count() == 6 # root, "ca", "r", "t"(cat), "t"(cart), "dog"
rt.insert("ca")
assert rt.search("ca") and rt.node_count() == 6 # "ca" already a node, just flag it
print("radix ok")
The same four words that needed 9 trie nodes need 6 radix nodes: root, ca, r (= car), t (= cat), t (= cart) and dog. The single-child chain d → o → g collapsed into one edge.
Variant: a ternary search tree
Each node holds one character and three children: lo (smaller character, same position), eq (this character matched, next position) and hi (larger character, same position). It is a trie whose child maps are binary search trees.
class TSTNode:
__slots__ = ("ch", "lo", "eq", "hi", "end")
def __init__(self, ch: str) -> None:
self.ch, self.lo, self.eq, self.hi, self.end = ch, None, None, None, False
class TST:
def __init__(self) -> None:
self.root: TSTNode | None = None
def insert(self, word: str) -> None:
assert word, "empty keys are not stored in a TST"
self.root = self._insert(self.root, word, 0)
def _insert(self, node: TSTNode | None, w: str, i: int) -> TSTNode:
ch = w[i]
if node is None:
node = TSTNode(ch)
if ch < node.ch:
node.lo = self._insert(node.lo, w, i)
elif ch > node.ch:
node.hi = self._insert(node.hi, w, i)
elif i + 1 < len(w):
node.eq = self._insert(node.eq, w, i + 1)
else:
node.end = True
return node
def _find(self, w: str) -> TSTNode | None:
node, i = self.root, 0
while node is not None:
if w[i] < node.ch:
node = node.lo
elif w[i] > node.ch:
node = node.hi
elif i + 1 == len(w):
return node
else:
node, i = node.eq, i + 1
return None
def search(self, w: str) -> bool:
node = self._find(w) if w else None
return node is not None and node.end
def starts_with(self, p: str) -> bool:
return not p or self._find(p) is not None
tst = TST()
for w in ["car", "cat", "cart", "dog"]:
tst.insert(w)
assert tst.search("car") and tst.search("cart") and tst.search("dog")
assert not tst.search("ca") and tst.starts_with("ca") and not tst.starts_with("cb")
print("tst ok")
Each node is a fixed three pointers plus a character, regardless of alphabet size, which is why TSTs suit large alphabets. Search costs eq steps plus the lo/hi steps inside each level's BST; inserting keys in random order keeps those BSTs shallow.
Real-world uses
- IP forwarding: longest-prefix match. A router's forwarding table maps prefixes (
10.0.0.0/8,10.1.0.0/16,0.0.0.0/0) to next hops, and each packet takes the longest matching prefix. In software, this is a binary trie over address bits, always compressed: 4.3BSD-Reno introduced a Patricia-style radix tree for the routing table (Keith Sklower, "A Tree-Based Packet Routing Table for Berkeley Unix", USENIX 1991), still visible in the BSDs, and the Linux kernel's IPv4 FIB uses a level-compressed trie (fib_trie, after Nilsson and Karlsson's LC-trie, IEEE JSAC 1999), where dense subtrees are replaced by a single node indexing several bits at once. Hardware routers use TCAMs instead. See the network layer lesson for the forwarding rule and BGP for where those prefixes come from. - Autocomplete services. Search boxes, IDEs and command palettes answer "top suggestions for this prefix" on every keystroke. The common architecture is a trie (or a sorted table) with precomputed top-k per prefix, built offline from query logs and served from memory, often sharded by the first characters of the prefix. Recomputing the lists in batch rather than updating them live is the standard trade.
- Ethereum's state: the Merkle Patricia trie. Ethereum stores account state, transactions and receipts in a "modified Merkle Patricia trie" (Ethereum Yellow Paper, Appendix D). Keys (for the state trie, the Keccak-256 hash of the account address) are walked as hexadecimal nibbles, so branch nodes have 16 children plus a value slot; extension nodes compress single-child chains (the Patricia part); leaf nodes hold the remaining key suffix and the value. Every node is referenced by the hash of its encoding (the Merkle part), so the root hash commits to the entire state and a light client can verify one account with a proof of nodes. It is the textbook example of a radix trie whose node layout is chosen for authenticated proofs rather than speed.
- Redis rax. Redis implements a radix tree in
rax.cand uses it for Streams: stream entry IDs (<milliseconds>-<sequence>, stored as 128-bit big-endian keys) map to listpack-encoded blocks of entries, so IDs sharing a time prefix share nodes and range scans follow key order. Redis also uses rax in several internal tables (for example consumer-group pending-entry lists). The Redis internals page covers rax's node layout. - Databases. In-memory database indexes use adaptive radix trees (HyPer and DuckDB use ART for indexes). PostgreSQL's SP-GiST access method supports radix-tree indexes over text and IP addresses (the
inetoperator classes). See the indexing deep dive. - Search engines' term dictionaries. Lucene stores its term index as a finite-state transducer, a minimal automaton that shares suffixes as well as prefixes (the DAWG idea below). See search engineering.
- Spell checkers and keyboards. Prefix trees and DAWGs over a dictionary let a spell checker enumerate candidate corrections within an edit distance by walking the trie with a dynamic-programming row per node.
- Aho–Corasick. Multi-pattern string search (antivirus signatures,
grep -Fwith many patterns, intrusion detection) builds a trie of the patterns and adds failure links. That is a later lesson; the trie is its skeleton.
Pitfalls & edge cases
- Confusing "is a prefix" with "is a word".
search("ca")must be false after insertingcar. Always check the end flag;startsWithis the one that ignores it. - The empty string. The root represents it.
startsWith("")is true;search("")is true only if someone inserted"". Decide what your API means and test it; inserting""should setroot.end. - Deleting a word that is not present. Without the
searchguard, the decrement loop corrupts counters or crashes on a missing child. Also guard against deleting a word that is only a prefix (delete("ca")when onlycarexists). - Pruning too much. A node with no children may still be an end-of-word (
carafter deletingcart). Prune on "no children and not end" — or, with counters, onpass == 0, which encodes both. - Character mapping.
ch - 'a'crashes or corrupts memory on uppercase, digits or Unicode. Validate input or use a map. In Java,charAtgives UTF-16 code units, so a character outside the Basic Multilingual Plane is two symbols. - XOR trie bit width. All numbers must be inserted with the same width , starting from the top bit. Using
x.bit_length()per number silently compares bits of different weights. Choose from the constraint (, or simply 31/32/63). - Signed integers in XOR tries. Negative numbers in two's complement have the top bit set; if negatives are allowed, either offset values or treat the sign bit with inverted preference. In JavaScript use
>>>and avoid|=on bit 31, which produces a negative number. - Querying an empty XOR trie. The greedy walk follows a missing child into node 0 and returns garbage. Check emptiness first (the offline problem returns -1).
- Memory blow-up. Array-of-26 nodes for inserted characters cost hundreds of megabytes. Estimate node size before choosing the representation. Pre-size pools in contests: maximum nodes = total characters + 1.
- Recursion depth. Recursive insert/delete on keys of length overflows Python's default recursion limit and native stacks. Write the walks iteratively.
- Duplicates. A boolean flag cannot represent "inserted twice, deleted once". Use counters if the problem is a multiset.
- Word Search II duplicates. The same word can be found along several paths; clear it from the end node on first discovery.
Variations
- Compressed trie / radix tree / Patricia. Collapse single-child chains into edges labelled with strings. With keys, at most nodes, independent of key lengths. Morrison's original PATRICIA is the binary version that stores only a bit index to test at each internal node and checks the full key at the leaf; it never needs to compare skipped bits during descent. Insertion splits an edge; deletion may merge a node with its only remaining child.
- Level-compressed trie (LC-trie). Replace a complete subtree of depth with one node of children, so one step consumes bits. Used by Linux routing.
- Adaptive radix tree (ART). Byte-wise radix tree with four node sizes (4, 16, 48, 256) chosen per node by fill, plus path compression. Lookups touch few nodes and nodes fit cache lines.
- Ternary search tree. Three pointers per node, BST within each level. Memory independent of alphabet size; supports ordered iteration, prefix search and near-neighbour search (Bentley and Sedgewick, "Fast Algorithms for Sorting and Searching Strings", SODA 1997; their companion "Ternary Search Trees", Dr. Dobb's 1998).
- DAWG / minimal acyclic automaton. A trie shares prefixes; a directed acyclic word graph also shares suffixes, by merging equivalent subtrees (nodes whose sets of completions are identical). For a dictionary of English words, suffixes like
-ing,-tionand-ersare stored once. Daciuk, Mihov, Watson and Watson ("Incremental construction of minimal acyclic finite-state automata", Computational Linguistics 26(1), 2000) build it in one pass over sorted input. A DAWG can answer membership but cannot attach a different value to each word unless it becomes a transducer (FST) that emits output along edges — Lucene's choice. - Suffix trie / suffix tree / suffix automaton. Insert every suffix of one text to answer substring queries. The naive suffix trie has nodes; the compressed suffix tree (Weiner 1973, McCreight 1976, Ukkonen 1995) has ; the suffix automaton (Blumer et al., 1985 — also called the DAWG of the text) is the minimal automaton. Covered in the string module.
- Bitwise trie with counts. The XOR trie plus a counter per node answers "how many stored have ": walk the bits of ; whenever has a 1 bit, add the count of the subtree that would make that XOR bit 0. That gives pair counting in (LeetCode 1803).
- Persistent trie. Path copying on insert keeps every version; a persistent XOR trie answers "max XOR of with an element in positions " by storing counts and walking two versions at once. The same idea powers persistent segment trees in the segment trees lesson.
- Hash-based alternatives. A hash set of all prefixes (rung 2) or a sorted array with binary search (rung 3). Often the right answer for static data.
Practice ladder
Each problem is described in my own words; follow the link for the formal statement.
1. Implement Trie (Prefix Tree) (LeetCode 208) — Implement insert, search and startsWith. Teaches the end-of-word flag versus the prefix walk.
Hint
Write one private walk(s) that returns the node or null. search and startsWith differ only in whether they check the flag.
2. Longest Word in Dictionary (LeetCode 720) — Find the longest word that can be built one letter at a time from other words in the list (ties: smallest lexicographically). Teaches traversing only through end-of-word nodes.
Hint
Insert all words, then DFS (or BFS) from the root, only stepping into children that are themselves end-of-word. Visit children in alphabetical order to get the tie-break free.
3. Replace Words (LeetCode 648) — Replace every word in a sentence by its shortest dictionary root. Teaches the "stop at the first end node" walk, which is longest-prefix match turned around. The solution is the replace_words variant above.
Hint
Insert the roots. For each word walk the trie; return the prefix as soon as you hit an end node, or the whole word if an edge is missing.
4. Map Sum Pairs (LeetCode 677) — Insert key/value pairs (re-inserting overwrites) and return the sum of values of keys with a given prefix. Teaches storing aggregates on nodes and handling overwrite deltas.
Hint
Keep a separate map of current values. On insert, compute delta = new - old and add delta to every node along the path; the prefix query reads one node.
Solution
class MapSum:
def __init__(self) -> None:
self.root: dict = {"#": 0}
self.vals: dict[str, int] = {}
def insert(self, key: str, val: int) -> None:
delta = val - self.vals.get(key, 0)
self.vals[key] = val
node = self.root
node["#"] += delta
for ch in key:
node = node.setdefault(ch, {"#": 0})
node["#"] += delta
def sum(self, prefix: str) -> int:
node = self.root
for ch in prefix:
if ch not in node:
return 0
node = node[ch]
return node["#"]
m = MapSum()
m.insert("apple", 3)
assert m.sum("ap") == 3
m.insert("app", 2)
assert m.sum("ap") == 5
m.insert("apple", 1) # overwrite: delta -2
assert m.sum("ap") == 3 and m.sum("apple") == 1 and m.sum("b") == 0
print("677 ok")
per operation. The key "#" cannot collide with a lowercase letter.
5. Search Suggestions System (LeetCode 1268) — After each typed character, list up to three products with that prefix in lexicographic order. Teaches top-k per node (the Autocomplete variant above passes it) or the sorted-array alternative.
Hint
Either store the 3 smallest words at each node during insertion, or sort the products and binary-search the start of the prefix block for each typed prefix, taking the next three that still match.
6. Design Add and Search Words Data Structure (LeetCode 211) — Search patterns where . matches any single letter. Teaches DFS branching inside the trie.
Hint
Recurse on (node, index). At a ., try every child; otherwise follow the one matching child. Worst case , but the trie keeps it small in practice.
Solution
class WordDictionary:
def __init__(self) -> None:
self.root: dict = {}
def add_word(self, word: str) -> None:
node = self.root
for ch in word:
node = node.setdefault(ch, {})
node["$"] = True
def search(self, word: str) -> bool:
def dfs(node: dict, i: int) -> bool:
if i == len(word):
return "$" in node
ch = word[i]
if ch == ".":
return any(dfs(child, i + 1) for key, child in node.items() if key != "$")
return ch in node and dfs(node[ch], i + 1)
return dfs(self.root, 0)
wd = WordDictionary()
for w in ["bad", "dad", "mad"]:
wd.add_word(w)
assert not wd.search("pad") and wd.search("bad") and wd.search(".ad") and wd.search("b..")
assert not wd.search("b...") and not wd.search(".")
print("211 ok")
Exact searches are ; a pattern with dots costs up to .
7. Maximum XOR of Two Numbers in an Array (LeetCode 421) — Find the largest XOR of any pair. The canonical XOR trie problem; the implementation above solves it.
Hint
Insert each number's 31 bits from the top. For each number, walk preferring the opposite bit. There is also a hash-set solution that builds the answer bit by bit using prefixes — worth knowing as the follow-up.
8. Vasiliy's Multiset (Codeforces 706D) — A multiset supports insert, delete-one-copy and "max XOR with x". Teaches the XOR trie with counters so deletion works.
Hint
Keep a count per node; insert increments along the path, delete decrements. In the query, treat a child with count 0 as missing. Insert 0 at the start as the problem requires.
Solution
def vasiliy(ops: list[tuple[str, int]]) -> list[int]:
B = 30
child, cnt = [[0, 0]], [0]
def update(x: int, d: int) -> None:
node = 0
cnt[0] += d
for b in range(B - 1, -1, -1):
bit = (x >> b) & 1
if not child[node][bit]:
child[node][bit] = len(child)
child.append([0, 0])
cnt.append(0)
node = child[node][bit]
cnt[node] += d
def query(x: int) -> int:
node, res = 0, 0
for b in range(B - 1, -1, -1):
bit = (x >> b) & 1
nxt = child[node][bit ^ 1]
if nxt and cnt[nxt] > 0:
res |= 1 << b
node = nxt
else:
node = child[node][bit]
return res
update(0, 1) # the multiset always contains 0
out = []
for op, x in ops:
if op == "+":
update(x, 1)
elif op == "-":
update(x, -1)
else:
out.append(query(x))
return out
ops = [("+", 8), ("+", 9), ("+", 11), ("+", 6), ("+", 1), ("?", 3), ("-", 8), ("?", 3), ("?", 8), ("?", 11)]
assert vasiliy(ops) == [11, 10, 14, 13]
print("706D ok")
per operation.
9. Maximum XOR With an Element From Array (LeetCode 1707) — Queries : best XOR with an element not exceeding . Teaches offline processing; the maximize_xor variant above is the solution.
Hint
Sort numbers ascending and queries by . Insert numbers while they are , then query. Answer when nothing has been inserted.
10. Word Search II (LeetCode 212) — Find all dictionary words traceable in a letter grid. Teaches trie + backtracking with pruning; the find_words variant above passes it.
Hint
One DFS per cell that walks the trie alongside the grid. Store full words at end nodes, pop them when found, and delete exhausted trie nodes on the way back.
11. Stream of Characters (LeetCode 1032) — After each streamed letter, report whether some suffix of the stream is a word. Teaches the reversed-word trie.
Hint
Insert every word reversed. Keep the last maxLen characters; on each query walk the trie from the newest character backwards and stop at the first end node or missing edge.
12. Count Pairs With XOR in a Range (LeetCode 1803) — Count pairs whose XOR lies in . Teaches counting with a bitwise trie: f(hi + 1) - f(lo) where f(k) counts pairs with XOR below .
Hint
For each number, before inserting it, walk the bits of . When bit of is 1, all stored numbers in the child that makes the XOR bit 0 qualify: add that child's count and continue in the other child.
Solution
def count_pairs(nums: list[int], low: int, high: int) -> int:
B = 15 # values < 2**15 in this problem
def below(k: int) -> int: # pairs i < j with nums[i] ^ nums[j] < k
child, cnt = [[0, 0]], [0]
total = 0
for x in nums:
node = 0
for b in range(B - 1, -1, -1):
if node == -1:
break
xb, kb = (x >> b) & 1, (k >> b) & 1
if kb:
same = child[node][xb] # XOR bit 0 < 1: whole subtree counts
if same:
total += cnt[same]
node = child[node][xb ^ 1] or -1
else:
node = child[node][xb] or -1
node = 0
for b in range(B - 1, -1, -1):
bit = (x >> b) & 1
if not child[node][bit]:
child[node][bit] = len(child)
child.append([0, 0])
cnt.append(0)
node = child[node][bit]
cnt[node] += 1
return total
return below(high + 1) - below(low)
def brute(nums: list[int], low: int, high: int) -> int:
n = len(nums)
return sum(low <= nums[i] ^ nums[j] <= high for i in range(n) for j in range(i + 1, n))
assert count_pairs([1, 4, 2, 7], 2, 6) == 6
assert count_pairs([9, 8, 4, 2, 1], 5, 14) == 8
data = [(i * 7919) % 1000 for i in range(60)]
assert count_pairs(data, 100, 700) == brute(data, 100, 700)
print("1803 ok")
.
13. Palindrome Pairs (LeetCode 336) — Find all ordered pairs of distinct words whose concatenation is a palindrome. Teaches a trie of reversed words with "remaining suffix is a palindrome" lists on nodes. Hard and fiddly.
Hint
Insert each word reversed; at every node store the indices of words whose remaining (not yet consumed) part is a palindrome. For each word, walk it through the trie: an end node mid-walk whose word leaves a palindromic tail of the current word is a pair; at the end of the walk, the stored palindrome-remainder list gives the rest.
14. Perfect Security (Codeforces 923C) — Given a ciphertext array and a multiset of keys, permute the keys to make the decrypted message lexicographically smallest. Teaches the greedy "minimum XOR" walk with deletion.
Hint
Lexicographically smallest means minimize the first element, then the second, … For each ciphertext value in order, take the stored key that minimizes XOR (prefer the same bit), then delete it from a counted XOR trie.
Common mistakes & interview follow-ups
"Why not a hash set?" For exact lookups a hash set is simpler and usually faster (fewer cache misses). The trie earns its keep when the questions involve prefixes: counting, enumerating, autocomplete, longest-prefix match, wildcard matching. Say both halves.
"How much memory will this use for 1 million words?" Bound the nodes by total characters + 1, then multiply by node size: array-of-26 nodes at ~216 bytes each are hundreds of megabytes at the worst case; real dictionaries share prefixes so the count is lower. Offer the fixes: hash-map or sorted children, compressed (radix) trie, a TST, or a DAWG if the set is static.
"The dictionary does not fit in memory." Store it on disk as a sorted file with a sparse in-memory index (the sorted-array rung, as SSTables do), or as a compact FST like Lucene. Prefix queries become a seek plus a sequential scan.
"Can you support deletion?" Yes: counters plus pruning, as above. Mention the guard for non-existent words and the "do not prune end-of-word nodes" rule.
"Make autocomplete return the top 5 by popularity." Precompute top-k at each node, query, insert, references per node of memory. Mention rebuild-offline for score changes, and storing top-k only to a limited depth.
"Unicode?" Hash-map children keyed by code point, or a byte-wise trie over UTF-8 (alphabet 256, used by ART and many tokenizers). Beware of normalization: é can be one code point or two.
"What about concurrency?" Read-mostly tries are often rebuilt and swapped atomically (copy-on-write). Lock-free concurrent tries exist (the Ctrie of Prokopec et al., 2012, used in Scala's TrieMap) — name it if asked.
"Max XOR of a subarray?" Prefix XORs turn it into max XOR of a pair of prefixes: insert , then for each prefix query and insert. Same .
"Max XOR with an element in index range [l, r], online?" Persistent XOR trie with counts: version minus version , walk both at once using count differences.
Common mistakes interviewers watch for: returning true from search for a mere prefix; not padding numbers to a fixed width in the XOR trie; recursion on long keys; deleting a node that is still an end-of-word; forgetting that an empty trie has a root.
Quick quiz
1. A trie stores words with total length . What is the maximum number of nodes, and when is it reached?
Answer
(the root plus one node per character), reached when no two words share a first character — every path is disjoint. Shared prefixes only reduce the count.
2. After inserting only cart, what do search("car") and startsWith("car") return, and why?
Answer
search("car") is false: the node for car exists (it is a prefix of cart) but its end flag is not set. startsWith("car") is true because the walk succeeds.
3. Why must the XOR trie consume bits from most significant to least significant?
Answer
Because the greedy choice is only safe when no later bit can outweigh it: . Going top-down, a 1 at the current bit beats any combination below. Going bottom-up, a 1 at a low bit can be outweighed by a later high bit, so greedy fails.
4. How many nodes does a compressed (radix) trie have for keys, at most, and why does key length no longer matter?
Answer
At most . Every node other than the root is either an end-of-word node (at most ) or a branching node with at least two children; a tree with at most "leaf-like" terminals has at most branching nodes. Single-child chains, which are what long keys create, are collapsed into edge labels.
5. Your autocomplete stores top-10 per node. A word's score drops sharply. What makes this update expensive?
Answer
The word may need to leave the top-10 list of every ancestor, and each such list must be refilled with the next-best word in that subtree, which may require looking into children's lists or a subtree search. Increases are easy (re-offer along the path); decreases are not, which is why systems rebuild periodically.
Further reading / sources
- Edward Fredkin, "Trie Memory", Communications of the ACM 3(9), 1960; René de la Briandais, "File Searching Using Variable Length Keys", Western Joint Computer Conference, 1959.
- Donald R. Morrison, "PATRICIA — Practical Algorithm To Retrieve Information Coded in Alphanumeric", Journal of the ACM 15(4), 1968.
- Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, section 6.3 "Digital Searching" — tries, digital search trees and Patricia, with analysis.
- Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed., section 5.2 "Tries" — R-way tries and ternary search tries with full code.
- Jon Bentley and Robert Sedgewick, "Fast Algorithms for Sorting and Searching Strings", SODA 1997.
- Viktor Leis, Alfons Kemper, Thomas Neumann, "The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases", ICDE 2013.
- Stefan Nilsson and Gunnar Karlsson, "IP-Address Lookup Using LC-Tries", IEEE Journal on Selected Areas in Communications 17(6), 1999; Keith Sklower, "A Tree-Based Packet Routing Table for Berkeley Unix", USENIX Winter 1991.
- Jan Daciuk, Stoyan Mihov, Bruce Watson, Richard Watson, "Incremental Construction of Minimal Acyclic Finite-State Automata", Computational Linguistics 26(1), 2000.
- Gavin Wood, Ethereum: A Secure Decentralised Generalised Transaction Ledger (Yellow Paper), Appendix D "Modified Merkle Patricia Tree".
- Redis source,
src/rax.handsrc/rax.c(antirez's radix tree), and the Redis Streams documentation. - cp-algorithms: Aho–Corasick (starts from the trie) and Antti Laaksonen, Competitive Programmer's Handbook, the trie section in chapter 26 "String algorithms".
Previous lesson: Heaps & Priority Queues · Next lesson: Segment Trees in Depth
Related: Module 3 overview · Trees overview · Hash Tables · Bit Manipulation · Backtracking & Recursion · String Algorithms · Strings in Depth · Fenwick Trees · Redis internals · Network layer · Course home