Tries
A tree of letters.
When you type CA on your phone, it suggests cat, car, and camera, instantly. That's powered by a trie. It's a tree where each step down is one letter, so words that share a beginning share a path.

- Type 'ca', get suggestions
- A tree of letters
- Shared beginnings share a path
Building a trie
Each node is a dictionary, from a letter to the next node. Insert walks down the word letter by letter, creating nodes as needed. A dollar sign marks where a complete word ends. Here we insert car, cat, and cap, and print the root. Run it. All three words share the C and the A.
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for ch in word:
node = node.setdefault(ch, {})
node["$"] = True
t = Trie()
for w in ["car", "cat", "cap"]:
t.insert(w)
print(t.root){'c': {'a': {'r': {'$': True}, 't': {'$': True}, 'p': {'$': True}}}}Trie costs
Inserting or finding a word takes O of L steps, where L is the length of the word. It doesn't matter if the trie holds ten words or ten million. That's why tries are used for autocomplete, spell checkers, and routing tables on the internet.
| key | value |
|---|---|
| Insert | O(length) |
| Find | O(length) |
| Prefix search | O(prefix length) |
| Used in | autocomplete, spell check |
Summary
A trie stores words letter by letter, so shared beginnings share a path. Lookups take O of word length. Next, using a trie for autocomplete.
Key takeaways- One letter per step
- $ marks a word
- O(length)