A signpost at every letter
Tries / Prefix Trees
The analogy
Imagine a hallway where each doorway is labelled with one letter. To find "car" you walk through C, then A, then R. Every word sharing the prefix "ca" walks the same first two doorways, so the shared beginning is stored exactly once — and standing in the "ca" room, everything reachable from here starts with "ca".
Visualizer
Walking the letters
step 1 / 7A trie holding car, cart, can and dog. Each edge is one letter; the root holds nothing.stored: car, cart, can, dog
class Trie:
def __init__(self):
self.children = {}
self.is_word = False
def insert(self, word):
node = self
for ch in word:
node = node.children.setdefault(ch, Trie())
node.is_word = True # matters!
def find(self, prefix):
node = self
for ch in prefix:
if ch not in node.children:
return None
node = node.children[ch]
return node # subtree = all completions
# lookup is O(len(word)), NOT O(number of words)Check yourself
A trie holds 10 million words. Cost of looking up a 5-letter word?