Overview
A Trie, or prefix tree, is a tree-shaped data structure keyed by the characters of strings. Words that share a common prefix share the same path from the root, so the structure stores an entire dictionary compactly.
Each edge represents one character and each node marks whether a word ends there. Because lookups walk one character at a time, the cost depends on word length, not on how many words the trie holds.
How Trie (Prefix Tree) works
- Start at the root and follow the child edge labelled by the first character of the word.
- For each remaining character, descend to the matching child, creating it if it does not exist.
- Mark the final node as a word end so search can distinguish a stored word from a mere prefix.
- Search and prefix queries walk the same path; a missing edge means the word or prefix is absent.
When to use it
- Autocomplete and type-ahead suggestions, listing every word under a typed prefix.
- Spell-checkers and dictionaries that need fast prefix and membership lookups.
- IP routing tables and word games, where shared prefixes save memory and time.
Complexity analysis
Insert and search both run in O(L) time, where L is the length of the word, independent of the number of stored words. Space can be large — up to O(total characters × alphabet size) — but shared prefixes reduce it substantially in practice.
Frequently asked questions
How is a trie better than a hash set for autocomplete?
A hash set can test exact membership but cannot enumerate all words with a given prefix; a trie walks straight to the prefix node and lists everything beneath it.
Does trie lookup slow down as more words are added?
No. Lookup cost is O(L) in the query length only, so a trie with a million words is no slower to search than one with a hundred.