Tries (prefix trees) explained: autocomplete in Python with tests and timings
A trie finds every word with a given prefix without looking at the others. Build one in Python, test it and see it beat a full scan by a wide margin.
A trie (say "try", from retrieval), also called a prefix tree, stores words letter by letter so that words with the same beginning share the same path. It is the classic structure for autocomplete, spell checkers, dictionary lookups and IP routing tables, and a frequent interview topic ("implement a trie", "word search II", "longest common prefix"). The code, tests and timings below were run with Python 3 before publishing.
The idea
Store car, card, care, careful and cat. A list repeats the letters c-a-r four times. A trie stores them once:
- the path c → a → r is shared by four words,
- at the node for
rwe mark "a word ends here" (becausecaris a word), - below it,
d,e → f → u → lcontinue to the longer words, c → a → tbranches off ata.
To find all words starting with car, walk three steps down, then collect everything below that node. You never look at dog or dot at all.
| Operation | Cost | Notes |
|---|---|---|
| Insert a word of length L | O(L) | One step per letter |
| Exact lookup | O(L) | Walk, then check the end marker |
| "Does any word start with this?" | O(L) | Walk only |
| Autocomplete | O(L + size of the answer) | Walk to the prefix, then visit its subtree |
The cost depends on the length of the word, not on how many words are stored. That is the whole appeal.
A working example
Save as trie.py:
import random
import string
import time
class Trie:
"""A prefix tree: each node maps a character to a child node."""
def __init__(self):
self.root = {}
self.size = 0
def insert(self, word):
node = self.root
for ch in word:
node = node.setdefault(ch, {})
if "$" not in node: # "$" marks the end of a stored word
node["$"] = True
self.size += 1
def _walk(self, text):
node = self.root
for ch in text:
node = node.get(ch)
if node is None:
return None
return node
def contains(self, word):
node = self._walk(word)
return node is not None and "$" in node
def starts_with(self, prefix):
return self._walk(prefix) is not None
def autocomplete(self, prefix, limit=5):
"""Return up to `limit` stored words that start with prefix, in alphabetical order."""
node = self._walk(prefix)
out = []
if node is None:
return out
def visit(n, path):
if len(out) >= limit:
return
if "$" in n:
out.append(prefix + "".join(path))
for ch in sorted(k for k in n if k != "$"):
visit(n[ch], path + [ch])
visit(node, [])
return out
def list_prefix_scan(words, prefix, limit=5):
"""The simple way: look at every word."""
return sorted(w for w in words if w.startswith(prefix))[:limit]
if __name__ == "__main__":
t = Trie()
for w in ["car", "card", "care", "careful", "cat", "dog", "do", "dot"]:
t.insert(w)
print("contains('car') :", t.contains("car"))
print("contains('ca') :", t.contains("ca"), "(a prefix, not a stored word)")
print("starts_with('ca') :", t.starts_with("ca"))
print("autocomplete('car') :", t.autocomplete("car"))
print("autocomplete('do', 2):", t.autocomplete("do", 2))
print("autocomplete('x') :", t.autocomplete("x"))
rnd = random.Random(2)
words = {"".join(rnd.choice(string.ascii_lowercase) for _ in range(rnd.randint(4, 10))) for _ in range(150_000)}
big = Trie()
t0 = time.perf_counter()
for w in words:
big.insert(w)
build = (time.perf_counter() - t0) * 1000
wl = list(words)
prefix = "qu"
n = 200
t0 = time.perf_counter()
for _ in range(n):
a = big.autocomplete(prefix)
t1 = (time.perf_counter() - t0) * 1000 / n
t0 = time.perf_counter()
for _ in range(n):
b = list_prefix_scan(wl, prefix)
t2 = (time.perf_counter() - t0) * 1000 / n
print(f"\n{len(words):,} words, build trie: {build:.0f} ms")
print(f"same answer for prefix '{prefix}': {a == b}")
print(f" trie autocomplete {t1:8.3f} ms per query")
print(f" scan every word {t2:8.3f} ms per query")
Output of python3 trie.py (the exact times depend on the machine):
contains('car') : True
contains('ca') : False (a prefix, not a stored word)
starts_with('ca') : True
autocomplete('car') : ['car', 'card', 'care', 'careful']
autocomplete('do', 2): ['do', 'dog']
autocomplete('x') : []
149,469 words, build trie: 716 ms
same answer for prefix 'qu': True
trie autocomplete 0.026 ms per query
scan every word 13.679 ms per query
How the code works
- Each node is a dictionary from a character to the next node. The special key
"$"marks the end of a stored word. This is howcontains('ca')is False whilestarts_with('ca')is True: the path exists but no word ends there. insertwalks down, creating nodes withsetdefault, then sets the end marker. Inserting a duplicate does not changesize.autocompletefirst walks to the prefix node. Then a depth-first visit goes through the children in sorted letter order, so the results come out alphabetically and stop at the limit.list_prefix_scanis the simple alternative: teststartswithon every word. It exists so that we can check the trie against a trusted answer.
Reading the timings
With about 150,000 random words and the prefix qu:
- Building the trie took 716 ms (one-time cost).
- A trie autocomplete took 0.026 ms per query.
- Scanning every word took 13.7 ms per query, roughly 500 times slower.
The scan gets slower in step with the number of words; the trie query does not. If you answer one query, scanning wins because it needs no build step. If you answer many queries on the same words, as a search box does, the trie wins easily.
Tests
Save as test_trie.py:
import random
import string
import unittest
from trie import Trie, list_prefix_scan
class TrieTests(unittest.TestCase):
def test_contains_vs_prefix(self):
t = Trie()
t.insert("car")
self.assertTrue(t.contains("car"))
self.assertFalse(t.contains("ca"))
self.assertTrue(t.starts_with("ca"))
self.assertFalse(t.starts_with("cb"))
def test_duplicates_counted_once(self):
t = Trie()
for w in ["a", "a", "ab"]:
t.insert(w)
self.assertEqual(t.size, 2)
def test_empty_prefix_lists_everything_sorted(self):
t = Trie()
for w in ["b", "a", "c"]:
t.insert(w)
self.assertEqual(t.autocomplete("", 10), ["a", "b", "c"])
def test_matches_simple_scan_on_random_words(self):
rnd = random.Random(4)
words = {"".join(rnd.choice("abc") for _ in range(rnd.randint(1, 6))) for _ in range(300)}
t = Trie()
for w in words:
t.insert(w)
for prefix in ["", "a", "ab", "abc", "cc", "zzz"]:
self.assertEqual(t.autocomplete(prefix, 7), list_prefix_scan(words, prefix, 7))
def test_limit_respected(self):
t = Trie()
for w in ["aa", "ab", "ac", "ad"]:
t.insert(w)
self.assertEqual(len(t.autocomplete("a", 2)), 2)
if __name__ == "__main__":
unittest.main()
$ python3 -m unittest
Ran 5 tests in 0.004s
OK
The most useful test compares the trie against the simple scan on random words and several prefixes, including an empty prefix and a prefix with no matches.
Trie or something else?
- Many prefix queries on a fixed or slowly changing set of words: trie.
- Exact lookups only: a hash set is simpler and faster. A trie is not needed.
- Sorted list plus binary search: also finds a prefix range in O(L log n) with far less memory. It is a fair alternative if the data rarely changes.
- Memory: a plain dictionary-per-node trie uses a lot of memory on large word sets. Compressed forms (radix tree, DAWG) and arrays for fixed alphabets reduce it.
Common mistakes
- Forgetting the end marker, so
carlooks like it is stored just becausecardis. - Confusing "prefix exists" with "word exists".
- Building the trie for a single query.
- Returning results in arbitrary order from autocomplete.
- Ignoring memory on millions of words, or ignoring case and accents (normalise the text first).
Main idea: a trie shares common beginnings, so prefix searches cost the length of the prefix plus the answer, not the size of the dictionary. Use it for autocomplete and prefix queries, and test it against a simple scan.
Interview prep and DSA series, Part 3 (more algorithms): 3 of 5. Previous: Heaps and priority queues explained: top-k, merging and task scheduling.
