Store words by their letters, sharing every common prefix. Lookup depends on word length, not dictionary size — which is why autocomplete stays instant no matter how many words you add.
Controls
Prefix Tree
step 0
Insight
Each edge is a character; each path from the root spells a prefix. Words sharing a prefix share the same nodes — stored once.
words0
nodes1
chars if stored flat0
saved by sharing0
Complexity
Search / insertO(L)
AutocompleteO(L + results)
SpaceO(total chars)
Trie (Prefix Tree)
The structure that makes autocomplete feel instant.
Before the details
A trie (from retrieval, usually pronounced "try") stores strings as paths through a tree. Each edge carries a character, so following a path from the root spells out a prefix. Words sharing a prefix share those nodes.
Lookup Does Not Care How Many Words You Have
Searching for a word of length L costs O(L) — one step per character. Crucially, that is independent of how many words the trie contains. A dictionary of ten words and one of ten million both answer a five-letter query in five steps.
Compare that with a balanced BST at O(L log n), where n is the dictionary size. The trie wins because it navigates by content rather than by comparison.
Prefix Queries Are the Real Superpower
A hash table can beat a trie for exact lookup — O(L) to hash versus O(L) to walk, with a smaller constant. But a hash table cannot answer "which words start with 'car'?" without scanning everything.
A trie answers it structurally: walk to the node for "car", then collect every word in the subtree beneath it. Press Autocomplete prefix and watch the subtree light up. That single property is why tries power search suggestions, IDE completion, and routing tables.
Marking Where Words End
Not every node is a word. Inserting "car" and "care" means "car" ends partway down the path to "care", so each node carries an is-word flag, drawn here as a filled circle.
Without it you could not tell whether a path spells a real word or merely a prefix of one — and searching for "ca" would wrongly succeed.
The Cost: Memory
Tries trade space for speed. A naive implementation gives every node an array of 26 child pointers, most of them null — enormously wasteful on sparse dictionaries.
Practical fixes: use a hash map of children instead of a fixed array, or switch to a radix tree (compressed trie), which merges chains of single-child nodes into one edge holding a whole substring. That is what IP routing tables use.
Watch the "saved by sharing" figure as you add words with common prefixes — sharing is what claws some of that memory back.
A tree where the path spells the word
A trie stores strings by their characters. Each edge is a character, so the path from the root to a node spells a prefix, and words sharing a prefix share that path.
Storing "cat", "car", "card", "dog":
root
/ \
c d
| |
a o
/ \ |
t* r* g*
|
d*
The asterisks mark nodes where a complete word ends — needed because "car" is a word and also a prefix of "card".
class TrieNode:
def __init__(self):
self.children = {}
self.is_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.is_word = node.is_word # no-op; kept for clarity
node.is_word = True
def search(self, word):
node = self._walk(word)
return node is not None and node.is_word
def starts_with(self, prefix):
return self._walk(prefix) is not None
def _walk(self, s):
node = self.root
for ch in s:
if ch not in node.children:
return None
node = node.children[ch]
return node
Every operation is O(length of the string) — independent of how many words are stored. That is the trie's defining property: looking up a 10-character word takes 10 steps whether the trie holds a hundred words or ten million.
What it does that a hash table cannot
A hash set answers "is this exact string present?" in O(1). A trie answers several questions a hash set cannot answer at all.
Query
Trie
Hash set
Exact lookup
O(m)
O(1) average
Does any word start with this prefix?
O(m)
O(n) — scan everything
All words with this prefix
O(m + output)
O(n)
Longest prefix of this string that is a word
O(m)
Not directly
Lexicographic iteration
Natural
Requires sorting
Fuzzy match within edit distance k
Feasible
Not directly
The prefix rows are the point. Autocomplete needs "all words starting with 'car'", and a trie walks three nodes and then collects the subtree. A hash set has no structure to exploit and must examine every key.
The longest-prefix match row matters in networking: IP routing tables answer "which routing rule has the longest matching prefix for this address?" and a trie over address bits does it in one pass. That is what a radix trie in a router is doing.
Space, and the two compressed variants
A naive trie is memory-hungry: one node per character per distinct prefix, and each node carries a dictionary. Storing a large English dictionary can use more memory than the strings themselves.
Two standard compressions:
Radix trie (Patricia trie) merges chains of single-child nodes into one edge labelled with a substring. A trie storing only "internationalisation" becomes two nodes rather than twenty-one. This is the variant used in routing tables and in some database indexes.
DAWG (directed acyclic word graph) also merges identical suffixes, so "running" and "jumping" share their "ing" ending. Far smaller, and it cannot store values per word, so it suits membership testing rather than mapping.
Structure
Space
Supports values
Standard trie
Largest
Yes
Radix trie
Much smaller
Yes
DAWG
Smallest
No
For most applications a standard trie with dictionary children is fine, and a radix trie is worth the extra complexity when the key set is large and shares long prefixes.
Lookup that ignores the dictionary size, and the memory bill for it
A trie's selling point is that finding a word costs the length of the word and nothing else -- the number of words stored does not appear in the complexity at all. That is easy to state and more convincing to measure, along with the memory it costs to make true.
example_01.pyPython
class Trie:
def __init__(self):
self.root = {}
self.nodes = 1
def add(self, word):
node = self.root
for ch in word:
if ch not in node:
node[ch] = {}
self.nodes += 1
node = node[ch]
node["$"] = True # marks a complete word
def find(self, word):
node, steps = self.root, 0
for ch in word:
steps += 1
if ch not in node:
return False, steps
node = node[ch]
return "$" in node, steps
def with_prefix(self, prefix):
node = self.root
for ch in prefix:
if ch not in node:
return []
node = node[ch]
out = []
def walk(n, so_far):
for k, v in n.items():
if k == "$":
out.append(prefix + so_far)
else:
walk(v, so_far + k)
walk(node, "")
return sorted(out)
words = ["car", "card", "care", "careful", "cat", "cats", "dog", "do",
"door", "dot"]
t = Trie()
for w in words:
t.add(w)
print("%d words stored in %d nodes" % (len(words), t.nodes))
print()
print("%-10s %8s %8s" % ("lookup", "found", "steps"))
for w in ("cat", "care", "cab", "careful", "zebra"):
found, steps = t.find(w)
print("%-10s %8s %8d" % (w, found, steps))
# The step count is the length of the word, never the size of the
# dictionary. "cab" failed in 3 steps and "zebra" in 1 -- a miss costs
# only as much as the matching prefix, so most misses are cheaper than
# hits. Add ten million more words and none of these numbers move.
#
# A hash table also gives O(1)-ish lookup. What it cannot do is this:
print()
for p in ("car", "do", "z"):
print('words starting with %-5r %s' % (p, t.with_prefix(p)))
# Prefix search is where the trie is not merely competitive but the only
# structure that answers the question directly. A hash of whole words has
# no way to find them without scanning every key; a sorted list can binary
# search to the first match, which is the real alternative and is why
# sorted arrays still power many autocomplete boxes.
#
# The cost is nodes. Every distinct prefix is an object:
print()
print("%-14s %8s %10s %14s" % ("dictionary", "words", "characters", "trie nodes"))
for name, ws in (("this example", words),
("shared prefixes", ["prefix%03d" % i for i in range(100)]),
("no sharing", ["%03dsuffix" % i for i in range(100)])):
tt = Trie()
for w in ws:
tt.add(w)
print("%-14s %8d %10d %14d" % (
name, len(ws), sum(len(w) for w in ws), tt.nodes))
# Compare the last two rows. Identical word count, identical total
# characters, and the trie is far smaller when the words share prefixes --
# because a shared prefix is stored exactly once. When they do not share,
# the trie approaches one node per character and the overhead of a
# dictionary per node makes it much heavier than the strings themselves.
#
# So the honest rule: a trie pays off on dictionaries with real prefix
# structure -- words in a language, URLs, IP prefixes, phone numbers --
# and is a poor choice for keys that look random, like hashes or UUIDs.
Output
Things to try
Load the sample words and note how car, card, care and careful all share one path for 'c-a-r'.
Insert a word starting with a new letter. A whole new branch appears from the root — nothing to share.
Search for 'car' after inserting 'card'. The path exists, but whether it is a word depends entirely on the end-of-word flag.
Autocomplete 'car'. Walk to that node, then every word beneath it is a completion — found without touching the rest of the dictionary.
Compare nodes with flat character count. The gap is exactly the memory prefix sharing saves.
Worth remembering
A trie stores strings as paths, sharing common prefixes. Lookup is O(word length) regardless of dictionary size, and prefix queries fall out of the structure for free — which no hash table can match. The price is memory, mitigated by hash-map children or radix compression.
Autocomplete, the canonical application
Collecting every word under a prefix is a DFS from the prefix's node:
def with_prefix(self, prefix, limit=10):
node = self._walk(prefix)
if node is None:
return []
out = []
def dfs(node, path):
if len(out) >= limit:
return
if node.is_word:
out.append(prefix + path)
for ch, child in sorted(node.children.items()):
dfs(child, path + ch)
dfs(node, "")
return out
Sorting the children gives lexicographic order; iterating unsorted is faster and gives arbitrary order.
Real autocomplete needs ranking, not just alphabetical order — the most popular completions first. The standard approach stores a score at each word node and, at each internal node, the best score in its subtree. A priority-queue traversal then emits completions in score order without exploring the whole subtree.
That refinement is what separates a working autocomplete from a fast one: without the subtree-maximum, finding the top 10 of a million completions requires visiting all of them.
Where tries are used
Autocomplete and type-ahead search in editors, search boxes and shells.
Spell checking — membership plus fuzzy matching within an edit distance, done by walking the trie while tracking a dynamic programming row.
IP routing tables — longest-prefix match on address bits, using a radix trie.
Word games — Boggle and Scrabble solvers prune impossible branches the moment a prefix leaves the trie.
T9 and predictive text on numeric keypads.
Aho-Corasick multi-pattern search — a trie of all patterns plus failure links, which finds every occurrence of many patterns in one pass.
Suffix tries and suffix trees for substring search and bioinformatics.
The word-game case illustrates the pruning value nicely: a Boggle solver walking a grid abandons a path as soon as the letters so far are not a prefix of any word, which removes almost all of an enormous search space.
Practical notes
Use a dictionary for children, not a fixed array of 26. The dictionary handles arbitrary alphabets, Unicode and case, and it does not waste space on absent characters.
Store values at word nodes if you need a map rather than a set — frequency, id, payload.
Deletion is fiddly. Removing a word means clearing is_word and then pruning nodes upwards while they have no children and are not words themselves. It is easy to prune too far and delete a shorter word's ending.
Consider whether you need one. For a few thousand strings and infrequent prefix queries, sorting the list and using bisect to find the prefix range is simpler and uses far less memory. A trie earns its place with many keys, frequent prefix queries, or shared long prefixes.
Questions people ask
How is a trie different from a binary search tree? A BST compares whole keys and branches two ways; a trie branches on one character at a time, with one child per possible next character.
Is a trie faster than a hash set for exact lookup? Usually slightly slower — O(m) character steps against one hash computation. Its advantage is prefix queries, not exact lookup.
How much memory does it use? Considerably more than the strings, in the naive form. Radix compression or a DAWG reduces it substantially.
Can it store non-string keys? Yes — any sequence. Tries over bytes, bits, integers as digit sequences, or lists of tokens all work.
What is Aho-Corasick? A trie of all search patterns with failure links, which matches every pattern against a text in one linear pass. It is what grep -F with many patterns uses.
Do I need is_word? Yes, whenever one word is a prefix of another — without it, "car" would be indistinguishable from a mere prefix of "card".
Recap in one screen
Each edge is a character, so the path spells a prefix and shared prefixes are stored once.
Every operation is O(word length), independent of how many words are stored.
Prefix queries are what a hash set cannot do: autocomplete, longest-prefix match, ordered iteration.
Space is the cost; radix tries merge single-child chains and DAWGs also merge suffixes.
Store a subtree-maximum score at each node if autocomplete needs ranked rather than alphabetical results.
Run it in Python
A trie built from a handful of words, with the node count printed against the character count so the sharing is visible. Then autocomplete, which is the operation a hash table cannot do at all.
trie.pyPython 3
# A trie: one node per character, with common prefixes shared.
class TrieNode:
def __init__(self):
self.children = {} # character -> TrieNode
self.is_word = False # does a word END here?
class Trie:
def __init__(self):
self.root = TrieNode()
self.nodes = 1
def insert(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
self.nodes += 1 # a genuinely new node
node = node.children[ch]
node.is_word = True # mark the end, do not add a node
def _walk(self, prefix):
node = self.root
for ch in prefix:
if ch not in node.children:
return None
node = node.children[ch]
return node
def contains(self, word):
node = self._walk(word)
return node is not None and node.is_word # both conditions matter
def starts_with(self, prefix):
return self._walk(prefix) is not None
def complete(self, prefix):
node = self._walk(prefix)
found = []
def collect(node, so_far):
if node.is_word:
found.append(so_far)
for ch, child in sorted(node.children.items()):
collect(child, so_far + ch)
if node:
collect(node, prefix)
return found
words = ["car", "card", "care", "careful", "cat", "dog", "do"]
trie = Trie()
for w in words:
trie.insert(w)
print("words :", words)
print("characters:", sum(len(w) for w in words))
print("trie nodes:", trie.nodes, "- shared prefixes are stored once")
print()
for probe in ["car", "ca", "cart", "do"]:
print(f" contains({probe!r:>8}) = {str(trie.contains(probe)):>5} "
f"starts_with = {trie.starts_with(probe)}")
print()
for prefix in ["car", "d", "z"]:
print(f" complete({prefix!r}) -> {trie.complete(prefix)}")
print()
print("Lookup costs O(length of the word) - the number of words never enters into it.")
Output
How the code works
self.children = {}A dictionary per node rather than a fixed array of 26. It costs more per node and handles any alphabet, including Unicode — the array version is faster and quietly assumes lowercase ASCII.
self.is_word = FalseThe flag is why "ca" is not a word even though the path exists, and why "do" is one even though "dog" continues past it. Without it a trie can only answer prefix questions.
for ch in word: node = node.children[ch]Lookup walks one node per character, so it costs O(length) no matter how many words are stored. A hash table also gets O(1)-ish, but it must hash the whole string first — also O(length).
trie.nodes vs sum(len(w))The saving is real but modest, and it comes entirely from shared prefixes. A trie over unrelated strings uses more memory than storing them in a set.
def collect(node, so_far):Autocomplete is a DFS from the prefix node. This is the operation a hash table simply cannot perform — hashing destroys the relationship between "car" and "card".
Change one thing
Insert "carpet" and re-print the node count. It adds three nodes, not six — car was already there.
Insert a hundred unrelated random strings and compare trie.nodes with the character count. The saving vanishes.
Add delete. The awkward part is knowing when a node may be removed: only when it ends no word and has no children.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
What does the is_word flag distinguish?
Without it a trie can only answer prefix questions - and "do" being a word while "dog" continues past it has nothing to do with being a leaf.
Trie lookup costs O(length of the word) because:
A million stored words cost the same as ten. A hash table is also roughly O(length), because it must hash the whole string.
The operation a hash table cannot do at all is:
Hashing destroys the relationship between "car" and "card". Autocomplete is a DFS from the prefix node, which needs the shared structure a trie keeps.
Cheat sheet
Trie (Prefix Tree)
Store words by their letters, sharing every common prefix. Lookup depends on word length, not dictionary size — which is why autocomplete stays instant no matter how many words you add.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.