2026-05-31
A trie (pronounced "try," from retrieval) is a tree where each node represents a character, and paths from root to node spell out keys. Hash maps give you O(1) lookup for an exact key, but they're useless for the questions tries answer cheaply: "what keys start with this prefix?" and "what's the shortest unique prefix of this key?"
Each node has up to k children (where k is your alphabet size) and a flag marking whether a complete word ends there. Lookup, insert, and delete are all O(m), where m is the length of the key — independent of how many keys are in the trie. That's the killer property: searching a trie with 10 million words takes the same time as one with 100 words.
Real-world example: autocomplete. When you type "java" into Google's search box and it suggests "javascript," "java tutorial," "java jobs" — that's a trie (or a more specialized variant like a radix tree or DAWG). The autocomplete service walks down the trie following your prefix, then collects all completions in the subtree below. With a hash map keyed on full strings, you'd have to scan every key to find prefix matches — O(n × m) instead of O(m + matches).
Other places tries earn their keep:
/users/:id/posts in O(path length), not O(routes).Rule of thumb for memory. A naïve trie with one child pointer per ASCII character per node uses ~512 bytes per node on a 64-bit system. Storing 1 million English words averaging 8 characters is ~8M nodes × 512B = ~4 GB. That's why production systems use compressed variants: radix tries (merge single-child chains into one node) and DAWGs (share common suffixes) routinely cut memory by 10–100×.
When NOT to use a trie: if you only ever do exact-match lookups and never prefix queries, a hash map is simpler, smaller, and faster in absolute terms (constant factors matter — O(1) hash lookup beats O(m) trie walk for typical key lengths). Reach for a trie when the queries, not just the keys, are prefix-shaped.