How to Build a Trie From Scratch in Python for Fast Prefix Search and Autocomplete
Build a trie from scratch in Python, reproduce two real bugs (a false-positive search and a delete that corrupts a sibling word), and benchmark it against a naive list scan.
Type the first few letters into any search box, product catalog, or command-line shell, and something has to answer the question “which of the things I know about start with this?” fast enough that it feels instant. A naive answer is to scan every stored item and check if it starts with what you typed. That works fine for a hundred items. It gets noticeably slow once you have hundreds of thousands, because the cost grows with both how many items you store and how long each one is.
Table Of Content
- What You Will Build
- Prerequisites
- Step 1: Why a Plain List Does Not Scale
- Step 2: A First Trie, With a Bug Baked In
- Step 3: Fix It With an End-of-Word Marker
- Step 4: Turn It Into Autocomplete
- Step 5: Rank Suggestions by What People Actually Pick
- Step 6: Benchmark the Trie Against the Naive List at Scale
- Step 7: Delete Without Corrupting a Sibling Word
- Step 8: Fix Deletion So Nothing Is Removed That Something Else Needs
- Putting It All Together
- Why This Matters Beyond Autocomplete: Trie in Your Own Router
- Common Mistakes and How to Verify Each Step Worked
- Confirming Everything Works End-to-End
- Next Steps
A trie (also called a prefix tree or digital tree) is a tree structure built specifically to answer prefix questions without scanning anything. Instead of storing whole words as single values, a trie spells each word out one character at a time as a path through the tree, so that every word sharing the same first few letters also shares the same first few nodes. Looking up a prefix means walking that path once, then reading off whatever hangs beneath it. Finding the path costs only as much as the prefix is long, never more, no matter how many words you have stored; you will measure in Step 6 how that plays out once you also have to collect the matches sitting beneath it.
In this tutorial you will build a trie from scratch in plain Python: no dependencies beyond the standard library. You will hit two real bugs along the way, both reproduced with actual code and actual wrong output, not described secondhand: a false-positive search bug from a missing “this is where a word ends” marker, and a data-corruption bug in a naive delete operation that silently destroys an unrelated word sharing a prefix with the one you meant to remove. You will also measure, with a real 50,000-entry benchmark, exactly how much a trie buys you (and where it does not help much at all).
What You Will Build
By the end of this tutorial you will have a complete, tested trie.py module that supports:
- Inserting words and checking whether an exact word is stored (
search) - Checking whether any stored word begins with a given prefix (
starts_with) - Autocomplete: listing every stored word that begins with a prefix
- Ranking those autocomplete results by how often users actually pick them, not by insertion order
- Safely deleting a word without corrupting any other word that happens to share a prefix with it
You will also have a ten-test pytest suite that locks in both of the real bugs this tutorial reproduces, so a future change that reintroduces either one fails loudly instead of shipping quietly.
Prerequisites
- Python 3.10 or later. This tutorial was built and verified on Python 3.13.
- Comfort with basic Python: classes, dictionaries, recursion. No prior knowledge of tries or trees is assumed; every term is defined before it is used.
- A terminal with
pipavailable. The only third-party package used ispytest, for the test suite.
python -m venv venv
venv\Scripts\activate # on Windows
# source venv/bin/activate # on macOS/Linux
pip install pytestThis tutorial used pytest 9.1.1.
Step 1: Why a Plain List Does Not Scale
Start with the obvious approach, so the trie’s benefit later has something concrete to be measured against. Given a list of product names, find every one that starts with a given prefix:
# step1_naive_list.py
PRODUCTS = [
"wireless mouse",
"wireless keyboard",
"wireless charger",
"wired headphones",
"usb-c cable",
"usb-c hub",
"webcam 1080p",
]
def naive_prefix_search(catalog, prefix):
"""Return every catalog entry that starts with prefix."""
return [item for item in catalog if item.startswith(prefix)]
for query in ("wireless", "usb-c", "web"):
matches = naive_prefix_search(PRODUCTS, query)
print(f"{query!r} -> {matches}")'wireless' -> ['wireless mouse', 'wireless keyboard', 'wireless charger']
'usb-c' -> ['usb-c cable', 'usb-c hub']
'web' -> ['webcam 1080p']This is correct, and for seven products it is instant. The problem is what it costs as the catalog grows: every single call has to look at every single item, checking up to the full length of the prefix against each one. Double the catalog size and this roughly doubles in cost, no matter how specific your prefix is. You will measure exactly how much this matters, with real numbers, in Step 7.
Step 2: A First Trie, With a Bug Baked In
A trie is built from nodes, where each node holds a dictionary mapping a single character to the next node in that character’s path. Here is a first version. It has a real bug in it on purpose, because the bug it contains is the single most common mistake people make the first time they build a trie, and seeing it fail is more instructive than being told to avoid it.
# step2_naive_trie_bug.py
class TrieNode:
def __init__(self):
self.children = {}
class BuggyTrie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
node = node.children.setdefault(char, TrieNode())
def search(self, word):
"""Bug: this only checks that a path exists, not that it ends a word."""
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return True
trie = BuggyTrie()
trie.insert("card")
print("insert('card')")
print("search('card') ->", trie.search("card"))
print("search('car') ->", trie.search("car"))
print("search('ca') ->", trie.search("ca"))
print("search('cart') ->", trie.search("cart"))insert('card')
search('card') -> True
search('car') -> True
search('ca') -> True
search('cart') -> FalseOnly the word “card” was ever inserted. Yet search('car') and search('ca') both come back True. Walk through why: insert creates a chain of nodes, one per character, c to a to r to d. search just walks that same chain and returns True the moment it reaches the end of the string you asked about, whether or not that string was ever actually inserted as a complete word. Since “car” and “ca” both happen to be prefixes of a path that exists, they falsely report as found. A trie without a way to mark “a real word ends here” cannot tell the difference between a word and a mere prefix of a longer word.
Step 3: Fix It With an End-of-Word Marker
The fix is a single boolean flag per node, set only when a word actually terminates at that node:
# step3_fixed_trie.py
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
node = node.children.setdefault(char, TrieNode())
node.is_end = True
def search(self, word):
node = self._walk(word)
return node is not None and node.is_end
def starts_with(self, prefix):
"""True if any stored word begins with prefix (prefix itself need not be a word)."""
return self._walk(prefix) is not None
def _walk(self, text):
node = self.root
for char in text:
if char not in node.children:
return None
node = node.children[char]
return node
trie = Trie()
trie.insert("card")
print("insert('card')")
print("search('card') ->", trie.search("card"))
print("search('car') ->", trie.search("car"))
print("search('ca') ->", trie.search("ca"))
print("starts_with('car') ->", trie.starts_with("car"))
print("starts_with('cart') ->", trie.starts_with("cart"))insert('card')
search('card') -> True
search('car') -> False
search('ca') -> False
starts_with('car') -> True
starts_with('cart') -> Falsesearch is now correct: it only returns True for words that were actually inserted. Notice the deliberate split from starts_with, which returns True for “car” even though “car” alone was never inserted, because it exists as a valid prefix of “card”. Autocomplete needs exactly this distinction: a user typing “car” should see “card” suggested, even though “car” by itself is not a word in the dictionary.
Step 4: Turn It Into Autocomplete
Autocomplete means: given a prefix, find every complete word stored beneath it. Walk to the node for the prefix, the same way starts_with does, then do a depth-first search from there, collecting every node along the way whose is_end flag is set.
# step4_autocomplete.py
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class AutocompleteTrie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
node = node.children.setdefault(char, TrieNode())
node.is_end = True
def _walk(self, text):
node = self.root
for char in text:
if char not in node.children:
return None
node = node.children[char]
return node
def autocomplete(self, prefix):
"""Return every stored word that starts with prefix."""
start_node = self._walk(prefix)
if start_node is None:
return []
results = []
self._collect(start_node, prefix, results)
return results
def _collect(self, node, path, results):
if node.is_end:
results.append(path)
for char, child in node.children.items():
self._collect(child, path + char, results)
PRODUCTS = [
"wireless mouse", "wireless keyboard", "wireless charger",
"wired headphones", "usb-c cable", "usb-c hub", "webcam 1080p",
]
trie = AutocompleteTrie()
for product in PRODUCTS:
trie.insert(product)
for query in ("wireless", "usb-c", "web"):
print(f"autocomplete({query!r}) -> {trie.autocomplete(query)}")
print()
print("case-sensitivity gotcha:")
trie.insert("Apple Watch")
print("autocomplete('Apple') ->", trie.autocomplete("Apple"))
print("autocomplete('apple') ->", trie.autocomplete("apple"))autocomplete('wireless') -> ['wireless mouse', 'wireless keyboard', 'wireless charger']
autocomplete('usb-c') -> ['usb-c cable', 'usb-c hub']
autocomplete('web') -> ['webcam 1080p']
case-sensitivity gotcha:
autocomplete('Apple') -> ['Apple Watch']
autocomplete('apple') -> []The autocomplete results are correct. The last two lines demonstrate a gotcha worth calling out explicitly: this trie is case-sensitive, because “A” and “a” are simply two different dictionary keys as far as children is concerned. That is not a bug so much as an unannounced design decision. A real search box almost always wants case-insensitive matching, and the fix is cheap: normalize every string to lowercase (or apply casefold() for broader Unicode correctness) both when you insert and when you query, and keep the original-cased string as a stored value if you still need to display it with its real capitalization.
Step 5: Rank Suggestions by What People Actually Pick
Plain autocomplete has a real usability problem once a prefix matches more than a handful of words: it returns them in whatever order the tree’s internal dictionaries happen to produce, which has nothing to do with which suggestion the user is likely to want. Fix this by tracking, per word, how many times it has actually been chosen, and sorting by that count.
# step5_ranked_autocomplete.py
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
self.frequency = 0
class RankedTrie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
node = node.children.setdefault(char, TrieNode())
node.is_end = True
def record_search(self, word):
"""Call this every time a user actually picks `word` from the results."""
node = self._walk(word)
if node is None or not node.is_end:
raise ValueError(f"{word!r} was never inserted")
node.frequency += 1
def _walk(self, text):
node = self.root
for char in text:
if char not in node.children:
return None
node = node.children[char]
return node
def autocomplete(self, prefix, limit=5):
start_node = self._walk(prefix)
if start_node is None:
return []
matches = []
self._collect(start_node, prefix, matches)
matches.sort(key=lambda pair: (-pair[1], pair[0]))
return [word for word, _freq in matches[:limit]]
def _collect(self, node, path, matches):
if node.is_end:
matches.append((path, node.frequency))
for char, child in node.children.items():
self._collect(child, path + char, matches)
PRODUCTS = [
"wireless mouse", "wireless keyboard", "wireless charger",
"wireless earbuds", "wireless router",
]
trie = RankedTrie()
for product in PRODUCTS:
trie.insert(product)
print("no searches recorded yet, tie-broken alphabetically:")
print(trie.autocomplete("wireless", limit=3))
for _ in range(50):
trie.record_search("wireless earbuds")
for _ in range(20):
trie.record_search("wireless charger")
for _ in range(5):
trie.record_search("wireless mouse")
print()
print("after 50/20/5 real searches, ranked by popularity:")
print(trie.autocomplete("wireless", limit=3))no searches recorded yet, tie-broken alphabetically:
['wireless charger', 'wireless earbuds', 'wireless keyboard']
after 50/20/5 real searches, ranked by popularity:
['wireless earbuds', 'wireless charger', 'wireless mouse']Before any searches are recorded, results fall back to alphabetical order, which is a sane, predictable default. Once real usage accumulates, “wireless earbuds” (50 picks) correctly jumps ahead of “wireless keyboard” (0 picks), even though “keyboard” sorts earlier in the alphabet. The sort key (-pair[1], pair[0]) is doing two things at once: the negated frequency sorts highest-first, and the word itself as a tiebreaker keeps output deterministic when two words have identical frequency, which matters for reproducible tests.
Step 6: Benchmark the Trie Against the Naive List at Scale
Now measure the actual payoff. Simulate a more realistic scenario: an internal admin tool’s search box, backed by 50,000 resource identifiers like user_1049283 or invoice_0021455, and compare a trie-based autocomplete against the plain list scan from Step 1.
# step6_benchmark.py
import random
import time
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
node = node.children.setdefault(char, TrieNode())
node.is_end = True
def autocomplete(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return []
node = node.children[char]
results = []
self._collect(node, prefix, results)
return results
def _collect(self, node, path, results):
if node.is_end:
results.append(path)
for char, child in node.children.items():
self._collect(child, path + char, results)
def build_corpus(size, seed=42):
"""Simulate resource identifiers from an internal admin search box."""
rng = random.Random(seed)
resource_types = ["user", "order", "invoice", "session", "customer", "ticket"]
words = []
for _ in range(size):
prefix = rng.choice(resource_types)
suffix = "".join(rng.choice("0123456789") for _ in range(7))
words.append(f"{prefix}_{suffix}")
return words
def naive_prefix_search(catalog, prefix):
return [item for item in catalog if item.startswith(prefix)]
corpus = build_corpus(50_000)
trie = Trie()
for word in corpus:
trie.insert(word)
queries = ["user_10", "order_5", "invoice_999", "customer_42"]
print(f"corpus size: {len(corpus):,} identifiers")
print()
for query in queries:
start = time.perf_counter()
naive_result = naive_prefix_search(corpus, query)
naive_elapsed = time.perf_counter() - start
start = time.perf_counter()
trie_result = trie.autocomplete(query)
trie_elapsed = time.perf_counter() - start
assert sorted(naive_result) == sorted(trie_result), "results diverged!"
speedup = naive_elapsed / trie_elapsed if trie_elapsed > 0 else float("inf")
print(
f"prefix={query!r:16} matches={len(naive_result):5} "
f"naive={naive_elapsed * 1000:8.3f}ms trie={trie_elapsed * 1000:8.3f}ms "
f"speedup={speedup:6.1f}x"
)The first time I ran this, it did not print a clean table. It crashed:
AssertionError: results diverged!That assertion exists specifically to catch a trie implementation that silently returns the wrong answer, and it caught a real bug in the very code shown above (in an earlier draft). The bug was in autocomplete: the original version had two separate for char in prefix loops, one to validate the path exists and a second to actually walk it, and the validation loop never updated node. It kept re-checking the root’s own immediate children on every character instead of descending the tree, so any prefix longer than one character that did not happen to have each of its individual letters appear as a first letter somewhere in the corpus was incorrectly reported as “not found.” Printing the buggy version’s actual behavior makes the failure concrete:
naive user_10 count: 80
buggy trie user_10 count: 0Eighty real matches for “user_10”, and the buggy trie found none of them, because “e” (the second character of “user_10”) is not the first letter of any resource type in the corpus, so the flawed check bailed out immediately. The fix, shown in the code above, is to fold both loops into one: check membership and advance node together, on every character, so the walk actually descends instead of repeatedly inspecting the root. With that fix in place, the benchmark runs cleanly:
corpus size: 50,000 identifiers
prefix='user_10' matches= 80 naive= 0.718ms trie= 0.062ms speedup= 11.5x
prefix='order_5' matches= 819 naive= 0.660ms trie= 0.526ms speedup= 1.3x
prefix='invoice_999' matches= 8 naive= 0.630ms trie= 0.009ms speedup= 68.5x
prefix='customer_42' matches= 83 naive= 0.624ms trie= 0.056ms speedup= 11.2xThis is worth reading carefully rather than skimming for the biggest number. Notice that the win is not uniform. “invoice_999” is a narrow, specific prefix with only 8 matches, and the trie wins by nearly 69 times, because it walks straight to the right subtree and barely has anything to collect. “order_5” is a broad prefix with 819 matches, and the trie’s advantage shrinks to just 1.3 times, because once the walk reaches the right subtree, it still has to visit every single matching node to collect all 819 results, and that collection cost is roughly the same amount of work the naive scan was already doing. The naive list scan pays a fixed cost proportional to the whole corpus on every call, no matter how narrow or broad the prefix is. The trie pays a cost proportional to the prefix length to find the right subtree, plus a cost proportional to the number of matches to collect them. A trie’s real advantage is biggest exactly when you need it most: narrow, specific, autocomplete-style prefixes with a handful of matches, which is the common case for a search box as someone is actively typing.
Step 7: Delete Without Corrupting a Sibling Word
Insertion and lookup are the easy operations. Deletion is where tries get genuinely tricky, because multiple words can share the same nodes, and removing one word’s nodes carelessly can break a completely different word that happens to share a prefix with it. Here is a naive delete that gets this wrong, reproduced with real, corrupted output:
# step7_naive_delete_bug.py
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
node = node.children.setdefault(char, TrieNode())
node.is_end = True
def search(self, word):
node = self._walk(word)
return node is not None and node.is_end
def _walk(self, text):
node = self.root
for char in text:
if char not in node.children:
return None
node = node.children[char]
return node
def delete(self, word):
"""Bug: removes every node on the path, even ones another word depends on."""
node = self.root
path = [node]
for char in word:
node = node.children[char]
path.append(node)
node.is_end = False
# Walk back to front, unconditionally unlinking each node from its parent.
for i in range(len(word), 0, -1):
parent = path[i - 1]
char = word[i - 1]
del parent.children[char]
trie = Trie()
trie.insert("car")
trie.insert("care")
print("insert('car'), insert('care')")
print("search('car') ->", trie.search("car"))
print("search('care') ->", trie.search("care"))
trie.delete("car")
print()
print("after delete('car'):")
print("search('car') ->", trie.search("car"))
print("search('care') ->", trie.search("care"), " (should still be True)")insert('car'), insert('care')
search('car') -> True
search('care') -> True
after delete('car'):
search('car') -> False
search('care') -> False (should still be True)Deleting “car” also silently deleted “care”, which was never asked for. The bug: delete walks back over every node on the “car” path and unconditionally unlinks each one from its parent, including the node for the second “r”, which “care” is still standing on top of (its own final “e” node hangs off that same “r” node). Nothing raised an exception. Nothing warned that another word depended on that node. It just quietly disappeared.
Step 8: Fix Deletion So Nothing Is Removed That Something Else Needs
The correct rule: only unlink a node from its parent if nothing else in the trie still needs it, meaning the node has no children of its own, and the node is not itself marking the end of some other, shorter word. Walk backward from the deleted word’s last node toward the root, and stop pruning the instant you hit a node that must be kept.
# step8_fixed_delete.py
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
node = node.children.setdefault(char, TrieNode())
node.is_end = True
def search(self, word):
node = self._walk(word)
return node is not None and node.is_end
def _walk(self, text):
node = self.root
for char in text:
if char not in node.children:
return None
node = node.children[char]
return node
def delete(self, word):
if not self.search(word):
raise KeyError(f"{word!r} is not stored in this trie")
node = self.root
path = [node]
for char in word:
node = node.children[char]
path.append(node)
path[-1].is_end = False
# Walk back to front, but only unlink a node if nothing else needs it:
# no children of its own, and it isn't itself the end of a shorter word.
for i in range(len(word), 0, -1):
current = path[i]
if current.children or current.is_end:
break
parent = path[i - 1]
char = word[i - 1]
del parent.children[char]
trie = Trie()
for word in ("car", "care", "cart"):
trie.insert(word)
print("insert('car'), insert('care'), insert('cart')")
for word in ("car", "care", "cart"):
print(f"search({word!r}) -> {trie.search(word)}")
trie.delete("car")
print()
print("after delete('car'):")
for word in ("car", "care", "cart"):
print(f"search({word!r}) -> {trie.search(word)}")
print()
print("deleting a word that was never inserted raises, instead of corrupting anything:")
try:
trie.delete("carbon")
except KeyError as exc:
print(f"KeyError: {exc}")insert('car'), insert('care'), insert('cart')
search('car') -> True
search('care') -> True
search('cart') -> True
after delete('car'):
search('car') -> False
search('care') -> True
search('cart') -> True
deleting a word that was never inserted raises, instead of corrupting anything:
KeyError: "'carbon' is not stored in this trie"Deleting “car” now leaves “care” and “cart” fully intact. It also guards against a second mistake: attempting to delete a word that was never inserted now raises a clear KeyError up front, via a search check before any mutation happens, rather than the naive version’s behavior of either silently doing nothing useful or crashing partway through with a confusing raw KeyError from inside the walk itself.
Putting It All Together
Here is the complete, consolidated module combining every fix above: end-of-word marking, prefix checks, ranked autocomplete, and safe deletion.
# trie.py
"""A from-scratch trie (prefix tree) with ranked autocomplete and safe deletion."""
class TrieNode:
__slots__ = ("children", "is_end", "frequency")
def __init__(self):
self.children = {}
self.is_end = False
self.frequency = 0
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
node = node.children.setdefault(char, TrieNode())
node.is_end = True
def search(self, word):
node = self._walk(word)
return node is not None and node.is_end
def starts_with(self, prefix):
return self._walk(prefix) is not None
def record_search(self, word):
node = self._walk(word)
if node is None or not node.is_end:
raise KeyError(f"{word!r} is not stored in this trie")
node.frequency += 1
def autocomplete(self, prefix, limit=5):
start_node = self._walk(prefix)
if start_node is None:
return []
matches = []
self._collect(start_node, prefix, matches)
matches.sort(key=lambda pair: (-pair[1], pair[0]))
return [word for word, _freq in matches[:limit]]
def delete(self, word):
if not self.search(word):
raise KeyError(f"{word!r} is not stored in this trie")
node = self.root
path = [node]
for char in word:
node = node.children[char]
path.append(node)
path[-1].is_end = False
for i in range(len(word), 0, -1):
current = path[i]
if current.children or current.is_end:
break
parent = path[i - 1]
char = word[i - 1]
del parent.children[char]
def _walk(self, text):
node = self.root
for char in text:
if char not in node.children:
return None
node = node.children[char]
return node
def _collect(self, node, path, matches):
if node.is_end:
matches.append((path, node.frequency))
for char, child in node.children.items():
self._collect(child, path + char, matches)TrieNode uses __slots__ here, which is not required for correctness but is worth knowing about: it stops Python from giving each node instance its own dynamic __dict__, which cuts per-node memory overhead. Measuring it directly with sys.getsizeof on this machine: a plain node instance without __slots__ reports 48 bytes for the instance itself, plus a separate 296-byte __dict__ to hold its three attributes, for 344 bytes total. The same node with __slots__ reports 56 bytes total, no separate dictionary at all, roughly a sixfold reduction per node. That matters for a trie specifically, because a trie with a large, diverse vocabulary can allocate a very large number of small node objects, often far more nodes than words.
Now the test suite that locks all of this in, including regression tests for both bugs reproduced above:
# test_trie.py
import pytest
from trie import Trie
def test_search_requires_full_word_not_just_a_path():
trie = Trie()
trie.insert("card")
assert trie.search("card") is True
assert trie.search("car") is False
assert trie.search("ca") is False
def test_starts_with_matches_partial_paths():
trie = Trie()
trie.insert("card")
assert trie.starts_with("car") is True
assert trie.starts_with("cart") is False
def test_search_missing_word_returns_false():
trie = Trie()
trie.insert("card")
assert trie.search("cards") is False
assert trie.search("zzz") is False
def test_autocomplete_returns_every_stored_word_with_prefix():
trie = Trie()
for word in ("wireless mouse", "wireless keyboard", "wired headphones"):
trie.insert(word)
assert sorted(trie.autocomplete("wireless")) == [
"wireless keyboard", "wireless mouse",
]
assert trie.autocomplete("nope") == []
def test_autocomplete_ranks_by_recorded_frequency():
trie = Trie()
for word in ("wireless mouse", "wireless keyboard", "wireless charger"):
trie.insert(word)
for _ in range(10):
trie.record_search("wireless charger")
assert trie.autocomplete("wireless", limit=1) == ["wireless charger"]
def test_record_search_on_unknown_word_raises():
trie = Trie()
trie.insert("card")
with pytest.raises(KeyError):
trie.record_search("cart")
def test_delete_removes_only_the_target_word():
trie = Trie()
for word in ("car", "care", "cart"):
trie.insert(word)
trie.delete("car")
assert trie.search("car") is False
assert trie.search("care") is True
assert trie.search("cart") is True
def test_delete_prunes_orphaned_nodes():
trie = Trie()
trie.insert("solo")
trie.delete("solo")
assert trie.root.children == {}
def test_delete_unknown_word_raises_and_leaves_trie_intact():
trie = Trie()
trie.insert("car")
with pytest.raises(KeyError):
trie.delete("carbon")
assert trie.search("car") is True
def test_case_sensitivity_is_exact_match_by_default():
trie = Trie()
trie.insert("Apple Watch")
assert trie.search("Apple Watch") is True
assert trie.search("apple watch") is False$ python -m pytest test_trie.py -v
collecting ... collected 10 items
test_trie.py::test_search_requires_full_word_not_just_a_path PASSED
test_trie.py::test_starts_with_matches_partial_paths PASSED
test_trie.py::test_search_missing_word_returns_false PASSED
test_trie.py::test_autocomplete_returns_every_stored_word_with_prefix PASSED
test_trie.py::test_autocomplete_ranks_by_recorded_frequency PASSED
test_trie.py::test_record_search_on_unknown_word_raises PASSED
test_trie.py::test_delete_removes_only_the_target_word PASSED
test_trie.py::test_delete_prunes_orphaned_nodes PASSED
test_trie.py::test_delete_unknown_word_raises_and_leaves_trie_intact PASSED
test_trie.py::test_case_sensitivity_is_exact_match_by_default PASSED
10 passed in 0.02sThe test named test_delete_prunes_orphaned_nodes is worth a second look: it inserts a single, unshared word, deletes it, and then asserts that the root’s children dictionary is completely empty afterward. That test would fail against the naive delete from Step 7 too, but for a different reason than the corruption bug: a delete implementation that only clears is_end flags and never actually removes any nodes would pass every search-based test while silently leaking memory forever, one orphaned node chain per deleted word. Testing the tree’s actual shape, not just what search reports, is what catches that class of bug.
Why This Matters Beyond Autocomplete: Trie in Your Own Router
Tries were independently described twice in computing history: first by René de la Briandais in 1959, then in 1960 by Edward Fredkin, who coined the name itself. According to Wikipedia’s Trie article, Fredkin pronounced it “tree,” “after the middle syllable of retrieval,” even though many people today pronounce it “try” specifically to avoid confusing it verbally with an ordinary tree. The same article notes that tries “are particularly effective for tasks such as autocomplete, spell checking, and IP routing, offering advantages over hash tables due to their prefix-based organization and lack of hash collisions,” and specifically that “searching for a node with an associated key of size m has the complexity of O(m),” independent of how many total keys are stored, unlike a hash table’s worst-case behavior.
The IP routing mention is not a throwaway example. Every time a packet crosses a router, the router has to find the most specific matching entry in its routing table for that packet’s destination address, a problem called longest prefix match. Wikipedia’s own Internet routing section states plainly: “Compressed variants of tries, such as databases for managing Forwarding Information Base (FIB), are used in storing IP address prefixes within routers and bridges for prefix-based lookup to resolve mask-based operations in IP routing.” This is not a historical curiosity. The Linux kernel’s own networking documentation describes exactly this mechanism as currently implemented: an LC-trie (level-compressed trie) backing the kernel’s Forwarding Information Base. Its lookup notes describe the same core algorithm you just built, extended to handle “no exact match” gracefully: “We descend the trie, key segment by key segment, until we find a leaf… If we don’t find a match, we enter prefix matching mode. The prefix length, starting out at the same as the key length, is reduced one step at a time, and we backtrack upwards through the trie trying to find a longest matching prefix.” Every time a Linux machine forwards a packet, it is walking a trie in essentially the same shape as the one you built in this tutorial, just keyed on the bits of an IP address instead of the characters of a product name.
Common Mistakes and How to Verify Each Step Worked
- Forgetting the end-of-word marker. If
search("car")returnsTrueafter only ever inserting “card”, you have Step 2’s bug. Verify by inserting one long word and searching for each of its proper prefixes; every one of them should returnFalsefromsearch(thoughTruefromstarts_with). - Assuming case-insensitivity for free. A trie treats “A” and “a” as unrelated keys unless you normalize case yourself, on both insert and lookup. Verify by inserting one mixed-case word and searching for it in a different case; if you want case-insensitive behavior and get
False, add normalization. - Deleting without checking what else depends on a node. If deleting one word makes a completely different, unrelated word stop being found, you have Step 7’s corruption bug. Verify with a three-line reproduction: insert two words where one is a prefix of the other (like “car” and “care”), delete the shorter one, and confirm the longer one still searches as
True. - Testing only through
search, never checking the tree’s actual shape. A delete that clears flags but never removes nodes passes every naive test while leaking memory forever. Verify by deleting every word you inserted and asserting the root’schildrendictionary ends up empty. - Assuming the trie always wins. As Step 6 showed, a broad prefix with hundreds of matches barely beats a linear scan, because collecting many results costs roughly the same either way. A trie’s biggest win is on narrow, specific prefixes with few matches, which is the common case while a user is still typing.
Confirming Everything Works End-to-End
Run the full test suite one more time from a clean checkout of just trie.py and test_trie.py, with no other files present, to confirm there is no hidden dependency on anything left over from the earlier, buggy steps:
$ python -m pytest test_trie.py -v
...
10 passed in 0.06sIf all ten tests pass on a fresh checkout, you have a trie that correctly distinguishes prefixes from real words, supports ranked autocomplete driven by real usage, and deletes words without corrupting anything that shares a prefix with them, the three properties this tutorial set out to build and break on purpose along the way.
Next Steps
If you found the “build a classic data structure from scratch, then break it on purpose” format useful, two more sxz.io Learning Hub tutorials follow the same pattern with different structures and different real bugs: an LRU cache built from a doubly linked list and a hash map, and a Bloom filter that trades a small, tunable false-positive rate for constant-size membership checks. Both reproduce their own real, working code and their own real bugs the same way this one did.
No Comment! Be the first one.