Tries and prefix trees

Key strings by their characters, not whole values. Shared prefixes share branches.

Cost is the key length, not the dictionary size

• Each edge = one character; each path = a prefix
• insert / search / starts_with: O(L)
• autocomplete: O(L + matches) — visits only matching words
• Independent of N (works the same at 10 or 10M words)

Watch prefixes share branches

cat, car, card, care share c-a-r. Green = word-end. "do" is both a word and a prefix of "dog"/"dot".

O(L) trie vs O(N·L) scan

Scan climbs with N; trie stays flat. 8× faster at 320000 words, and growing.

When (and when not)

• Yes: prefixes — autocomplete, spell-check, IP routing, dictionaries
• No: plain membership (a hash set is O(L), less memory)
• Memory-hungry → compressed trie / radix tree (IP routers)

Takeaway

Pick the structure whose cost doesn't grow with what grows. For prefixes, that's a trie. Next: range-query trees (segment, Fenwick).