Overview
Curated: · Written: · Reviewed:
Tries
A trie stores keys along paths rather than in nodes, which is why it answers prefix questions that hash structures cannot answer at all. This guide covers the structure's real cost model — lookup linear in key length rather than constant, and memory dominated by single-child chains — along with the end-of-key flag whose absence breaks every prefix-pair case, the compressed radix form and its edge split, and the ranking data that turns a trie into usable autocomplete. It also covers the automaton built from failure links that searches a text for many patterns in one pass, the binary trie over bit strings, and the production uses in routing and dictionaries, ending with the cases where a hash map or an inverted index is simply the better answer.
the trie as a prefix index
A trie stores keys along the paths of a tree rather than in its nodes, so a shared prefix is stored exactly once.
Each edge carries one symbol and each node represents the prefix spelled by the path from the root, which is what makes prefix queries a walk rather than a search.
The key is the path; no node holds a whole key.
root -> c -> a -> r ("car", end=True)
\-> d ("card", end=True)
\-> t ("cat", end=True)
"car", "card" and "cat" share the "ca" path, so that prefix is stored once.
Interview trap. Describing a trie as 'a tree of characters' misses the point: the key is the path, and no node holds a whole key.
Engineering practice. Reach for a trie when the queries are about prefixes; use a hash map when they are about whole keys.
lookup cost
Trie lookup costs O(k) in the key length, independent of how many keys are stored.
The walk descends one level per symbol, so a million-key trie and a thousand-key trie answer at the same cost for the same key.
O(k) in the key length, and a hash lookup is O(k) too - it must read the key to hash it.
trie.search("configuration") # 13 node hops, independent of corpus size
d["configuration"] # hashes 13 characters, then one probe
The notation differs; the work does not. Choose on query type and memory instead.
Interview trap. Comparing this with a hash map's O(1) ignores that hashing the key is itself O(k), so the two are closer than the notation suggests.
Engineering practice. Compare on the same terms — both are linear in key length — and decide on the query type and memory instead.
marking the end of a key
A node must carry an explicit end-of-key flag, because a stored key can be a proper prefix of another stored key.
Without the flag, a search for a short word succeeds whenever a longer word starting with it is present, since the path exists.
Without the flag, storing 'application' makes 'app' a member.
class Node:
__slots__ = ("children", "is_word")
def __init__(self): self.children, self.is_word = {}, False
trie.insert("application")
trie.search("app") # False only because is_word is checked
trie.starts_with("app") # True - a different question
Interview trap. Using 'the node has no children' as the end-of-key test fails for exactly the prefix case, and the bug is invisible until such a pair is stored.
Engineering practice. Store a boolean or a value at the node, and test with a pair where one key is a prefix of the other.
prefix search versus exact search
Testing whether any stored key starts with a prefix is the same walk as an exact lookup, minus the end-of-key check.
Reaching a node after consuming the prefix proves at least one key continues through it, which is the answer to the prefix question.
Same descent; the two entry points differ only in the final check.
def _descend(self, s):
node = self.root
for ch in s:
node = node.children.get(ch)
if node is None: return None
return node
def search(self, w): return (n := self._descend(w)) is not None and n.is_word
def starts_with(self, p): return self._descend(p) is not None
Interview trap. Implementing prefix search as an exact search that ignores failure conflates 'the prefix exists' with 'the prefix is a key'.
Engineering practice. Share the descent code and let the two entry points differ only in what they check at the final node.
enumerating completions
Listing every key under a prefix is a traversal of the subtree at the prefix node, costing time proportional to the output.
Because the subtree contains exactly the continuations, no filtering pass over unrelated keys is needed.
Cost is proportional to the output, not to the dictionary.
def completions(self, prefix, limit=10):
node, out = self._descend(prefix), []
stack = [(node, prefix)] if node else []
while stack and len(out) < limit: # bounded by what the UI shows
n, s = stack.pop()
if n.is_word: out.append(s)
for ch, child in n.children.items(): stack.append((child, s + ch))
return out
Scanning a 500,000-word list for the prefix would be 500,000 comparisons per keystroke.
Interview trap. Scanning all keys and testing the prefix is linear in the dictionary rather than in the answer, which is the difference autocomplete cares about.
Engineering practice. Descend once and traverse the subtree, and bound the traversal when the interface shows only the first few completions.
ranked autocomplete
Useful autocomplete needs ranking, which a plain trie does not provide, so a score is stored and propagated.
Storing the best score in each subtree at its root node lets a best-first traversal emit the top completions without visiting the whole subtree.
Store the best subtree score so a best-first walk can stop early.
node.best = max(node.best, score) # maintained on every insertion
# Best-first over subtrees using node.best returns the top 10 of a 200,000-word
# subtree after visiting a few dozen nodes, not 200,000.
Interview trap. Collecting all completions and sorting them is correct but costs time proportional to the subtree, which is unacceptable for a short common prefix.
Engineering practice. Store subtree maxima and use a priority queue over subtrees, updating the maxima on every insertion.
children as arrays versus maps
Representing children as a fixed array indexed by symbol is fast and wasteful; a hash map is compact and slower per step.
The array costs one slot per alphabet symbol per node whether used or not, while the map costs an entry per present child plus overhead.
26 slots per node is fast and wasteful; a dict is compact and slower per hop.
| Representation | Memory per node | Neighbour scan |
|---|---|---|
[None] * 26 | 26 pointers, used or not | O(1) index |
{} | one entry per present child | hash per hop |
[None] * 0x110000 (Unicode) | impossible | - |
Fix the alphabet from the real key domain before choosing.
Interview trap. Choosing a 26-slot array and then needing to support arbitrary Unicode requires rewriting every node operation.
Engineering practice. Decide the alphabet up front from the actual key domain, and prefer a map when it is large or open-ended.
memory as the real constraint
A naive trie's memory is dominated by nodes with a single child, which contribute a level of depth and no branching.
For natural-language dictionaries the node count can exceed the total character count of the keys, and each node carries child-pointer overhead.
Node count exceeds the character count of the keys in a naive trie.
# 100,000 English words, average length 8: 800,000 characters.
# A naive trie holds ~500,000 nodes even after prefix sharing, and each Python
# node object costs ~56 bytes plus its children dict: tens of megabytes for
# a word list whose raw text is under 1 MB.
Interview trap. Estimating trie memory from key sizes alone understates it by an order of magnitude in the array-children representation.
Engineering practice. Measure with real keys before committing, and consider a compressed variant when memory is the binding constraint.
the compressed trie
A radix tree collapses chains of single-child nodes into one edge labelled with a substring, cutting both depth and node count.
Insertion may need to split an existing edge when a new key diverges partway along it, which is the operation the plain trie does not have.
Radix edges hold substrings; the split is the operation the plain trie lacks.
Before inserting "cart": After:
root -> "car" (word) root -> "car" (word)
\-> "t" (word)
Inserting "ca" splits the same edge again: root -> "ca" -> "r".
Interview trap. The split case is easy to omit and only occurs when a new key shares a partial edge, so simple tests never reach it.
Engineering practice. Implement and test the edge split explicitly, including the case where the new key ends inside an existing edge.
tries versus hash maps
A hash map wins on memory and on plain lookups; a trie wins whenever the query is about prefixes, ordering, or nearest matches.
The trie's ordered structure supports lexicographic iteration and prefix ranges, neither of which a hash map can answer without a full scan.
A dict cannot answer a prefix question at all.
| Query | dict | trie |
|---|---|---|
| Is "cart" stored? | O(1) expected | O(k) |
| Any key starting "ca"? | O(n) scan | O(k) |
| All keys starting "ca" | O(n) scan | O(output) |
| Longest stored prefix of "cartel" | O(n) scan | O(k) |
Interview trap. Choosing a trie for exact-match lookups adds complexity and memory without buying anything.
Engineering practice. Justify a trie with a prefix or ordering query, and use the hash map otherwise.
wildcard matching
Supporting a single-symbol wildcard turns lookup into a branching search that must try every child at the wildcard position.
The cost becomes exponential in the number of wildcards in the worst case, because each one multiplies the number of live paths by the branching factor.
Each '.' multiplies the live paths by the branching factor.
def match(node, s, i):
if i == len(s): return node.is_word
if s[i] == ".":
return any(match(c, s, i + 1) for c in node.children.values()) # branches
child = node.children.get(s[i])
return bool(child) and match(child, s, i + 1)
# "...." over a 26-letter alphabet explores up to 26^4 = 456,976 paths.
Interview trap. Presenting wildcard search as still O(k) ignores the branching, which is the whole difficulty of the problem.
Engineering practice. State the branching cost, bound the number of wildcards accepted, and consider an inverted index when patterns are unconstrained.
the Aho-Corasick automaton
Searching a text for many patterns at once is done by adding failure links to a trie of the patterns, giving linear time in the text plus the matches.
A failure link points to the longest proper suffix of the current prefix that is also a prefix of some pattern, so a mismatch continues without restarting the scan.
One pass over the text finds every pattern, instead of one pass per pattern.
# 5,000 patterns, a 10 MB text.
# Naive: 5,000 x 10,000,000 = 5 x 10^10 character comparisons.
# Automaton: 10,000,000 steps plus one per match.
Interview trap. Running a separate search per pattern multiplies the text length by the pattern count, which is what the automaton exists to avoid.
Engineering practice. Build the automaton once per pattern set, and reuse it across texts when the patterns are stable.
building failure links
Failure links are computed by a breadth-first pass over the trie, because a node's link depends on its parent's.
Processing level by level guarantees the parent's link is already correct when the child's is computed, which is what makes the construction linear.
Breadth-first, so a node's parent link is already correct.
from collections import deque
q = deque()
for child in root.children.values():
child.fail = root # depth-1 fails to root; otherwise those links stay unset
q.append(child)
while q:
node = q.popleft()
for ch, child in node.children.items():
f = node.fail
while f and ch not in f.children: f = f.fail
child.fail = f.children[ch] if f and ch in f.children else root
q.append(child) # level order - depth-first reads an unset link
Interview trap. Computing links depth-first reads a parent link that has not been set, producing an automaton that silently misses matches.
Engineering practice. Use a queue for the construction, and verify the automaton against a naive multi-pattern search on random inputs.
the suffix trie and its size
A trie of all suffixes of a string answers substring queries in time linear in the query, but its naive size is quadratic in the text.
Compressing it into a suffix tree brings the size down to linear, and suffix arrays achieve similar queries with far smaller constants.
Quadratic nodes; a suffix array is linear and usually the right answer.
# Text of 1,000,000 characters:
# suffix trie ~ 5 x 10^11 nodes - unusable
# suffix tree ~ 2,000,000 nodes - large but possible
# suffix array = 1,000,000 ints = 8 MB, plus an LCP array
Interview trap. Proposing a suffix trie for a large text ignores the quadratic memory that makes it unusable beyond small inputs.
Engineering practice. Use a suffix array with a longest-common-prefix array for text indexing unless the specific queries demand the tree.
the binary trie for integers
Treating an integer as a bit string makes a trie over bits, which answers maximum-exclusive-or queries in time linear in the word width.
The query walks from the highest bit and prefers the opposite bit at each step, taking the same branch only when the preferred one is absent.
Walk from the high bit, preferring the opposite one.
def max_xor(trie, x, bits=32):
node, best = trie.root, 0
for b in range(bits - 1, -1, -1):
want = 1 - ((x >> b) & 1)
if want in node.children: best |= 1 << b; node = node.children[want]
else: node = node.children[1 - want]
return best
Fix the width: inserting 5 as 101 instead of 32 bits misaligns every comparison.
Interview trap. Trying to answer the same query with a hash map or sorting misses that the answer depends on bit-level prefixes rather than on value order.
Engineering practice. Fix the bit width explicitly, insert with leading zeros, and test values whose high bits differ.
deletion from a trie
Deleting a key clears its end-of-key flag and then removes nodes upward only while they have no children and no flag.
The upward pruning must stop at the first node that is still part of another key, which is why deletion is naturally recursive.
Prune upward only while a node has no children and no flag.
def delete(node, word, i=0):
if i == len(word): node.is_word = False
else:
child = node.children.get(word[i])
if child and delete(child, word, i + 1): del node.children[word[i]]
return not node.children and not node.is_word # safe to remove me
# Deleting "app" from {"app", "apple"} must keep the whole path.
Interview trap. Removing the whole path unconditionally deletes every other key sharing that prefix.
Engineering practice. Prune conditionally on the way back up, and test deleting a key that is a prefix of a remaining key.
counting with tries
Storing a count of keys in each subtree turns 'how many stored keys start with this prefix' into a single descent.
The count is incremented along the insertion path and decremented along the deletion path, so it stays consistent at O(k) cost per update.
Maintain the count on the mutation path; recomputing is a subtree walk.
def insert(self, word):
node = self.root
for ch in word:
node = node.children.setdefault(ch, Node())
node.count += 1 # O(k) per insert
def count_prefix(self, p):
node = self._descend(p)
return node.count if node else 0 # O(k) per query, not O(subtree)
Interview trap. Recomputing the count by traversing the subtree per query is linear in the subtree and defeats the purpose of the index.
Engineering practice. Maintain counts on the mutation paths, and assert them against a recomputation in tests.
alphabet size in the complexity
Trie complexities carry a factor of the alphabet size in operations that must inspect all children, and omitting it overstates performance.
Lookup is O(k) because it follows one child per level, but enumeration, wildcard search, and node compaction all touch every child slot.
Lookup is O(k); enumeration and wildcards carry the alphabet factor.
| Operation | Bound |
|---|---|
| insert / search / starts_with | O(k) |
| enumerate completions | O(output x k) |
| wildcard with w dots | O(k x A^w) |
| compaction / iteration of children | O(A) per node with array children |
Interview trap. Quoting O(k) for every trie operation hides the alphabet factor in exactly the operations where it matters.
Engineering practice. Name both parameters in the bound, and say which representation the alphabet factor depends on.
case, normalisation, and Unicode
A trie over text needs an explicit normalisation policy, because visually identical strings can have different code-point sequences.
Case folding, Unicode normalisation, and diacritic handling all change the key before it is inserted, and lookups must apply exactly the same transformation.
Normalise in one function used by both insert and lookup.
import unicodedata
def key(s): return unicodedata.normalize("NFC", s).casefold()
"café" == "cafe\u0301" # False - different code points
key("café") == key("cafe\u0301") # True
Normalising on insert but not on lookup produces stored keys that can never be found.
Interview trap. Normalising on insertion but not on lookup produces a structure where stored keys cannot be found, and the failures look random.
Engineering practice. Normalise in one function used by both paths, and record the policy so it can be reproduced when the index is rebuilt.
persistence and rebuild
Tries are usually rebuilt from source data rather than persisted node by node, because the structure is derivable and the pointers are not portable.
Rebuild time is linear in the total key length, which is usually acceptable at startup and avoids a serialisation format to maintain.
Rebuilding is linear in total key length; a node format couples to the refactor.
# 100,000 words, 800,000 characters: rebuild at startup is milliseconds.
trie = Trie()
for word in load_words(): trie.insert(word)
Interview trap. Serialising raw node structures couples the on-disk format to the in-memory representation and breaks on any refactor.
Engineering practice. Persist the key list and rebuild, or define an explicit format independent of the node layout.
concurrency
A trie under concurrent updates needs either immutability or fine-grained locking, because a single insertion touches a whole path.
Path-copying gives a persistent structure where readers see a consistent snapshot without locks, at the cost of allocating the modified path.
Path copying gives lock-free readers at the cost of allocating the modified path.
# An insert of a length-k key copies k nodes and swaps one root reference.
# Readers holding the old root see a consistent snapshot with no lock.
new_root = copy_path(root, word)
self.root = new_root # single atomic rebind
Interview trap. Locking the root serialises every operation and removes the scalability that the structure's independent paths would otherwise allow.
Engineering practice. Use an immutable trie with path copying for read-heavy workloads, and lock per node only with a measured need.
tries in routing and dictionaries
The production uses of tries are longest-prefix matching in network routing, autocompletion, and spell checking.
Longest-prefix matching is exactly the deepest end-of-key node encountered during a descent, which is a single walk rather than a search over rules.
Longest-prefix match is the deepest end-of-key node on one descent.
# Rules: 10.0.0.0/8 -> A, 10.1.0.0/16 -> B, 10.1.2.0/24 -> C
# Address 10.1.2.5 walks the bit trie and records the deepest rule seen: C.
# A scan over the rule list would be O(rules) per packet.
Interview trap. Implementing routing rules as a list scanned in order is correct but linear in the rule count, which does not hold up at internet scale.
Engineering practice. Model prefix rules as a trie, and record the matched depth so the longest match wins by construction.
the double-array and succinct forms
Space-optimised trie representations exist that cut memory by an order of magnitude at the cost of update flexibility.
Double-array and succinct encodings pack the structure into flat integer arrays, which is excellent for static dictionaries and poor for frequent updates.
An order of magnitude less memory, at the cost of updates.
| Form | Memory (100k words) | Update |
|---|---|---|
| Node objects | tens of MB | O(k) |
| Double array | a few MB | rebuild |
| Succinct (LOUDS) | under 1 MB | rebuild |
A static compiled index plus a small mutable overlay gets both.
Interview trap. Choosing a static representation for a workload with online updates makes every insertion a rebuild.
Engineering practice. Split the design into a static compiled index plus a small mutable overlay when both memory and updates matter.
testing a trie
Trie defects concentrate on prefix relationships, so tests must include keys that are prefixes of each other and the empty key.
The empty key is stored at the root, which is the one node whose end-of-key flag is easy to omit.
The empty key and prefix pairs are where the flag logic breaks.
t = Trie()
t.insert("")
assert t.search("") # the root's own flag
t.insert("app"); t.insert("apple")
t.delete("apple")
assert t.search("app") # pruning must stop at the shared path
Interview trap. Testing with a word list of similar lengths never produces the prefix-pair case that breaks the flag logic.
Engineering practice. Include the empty string, a key that is a prefix of another, and deletion of both, in every trie test suite.
when not to use a trie
If no query involves a prefix, an ordering, or a shared structure between keys, a trie is the wrong structure.
For exact lookups a hash map is smaller and faster; for ranked full-text search an inverted index is the right model.
No prefix query, no ordering, no shared structure - use the dict.
# Exact-match lookup of 100,000 UUIDs:
# dict - one hash, ~8 MB
# trie - 32 hops per lookup, no shared prefixes to exploit, far more memory
Interview trap. Introducing a trie because the keys are strings is a type-driven decision rather than a query-driven one.
Engineering practice. Name the prefix query the trie serves; without one, choose the simpler structure.