O(m) Insert and Lookup by Character — Not by Hash
Introduction to Tries
A trie (prefix tree) stores strings character-by-character so that insert and lookup both run in O(m) time where m is the word length, making it faster than a hash set for prefix-heavy workloads.
What you'll learn
- Describe the structure of a trie and how characters map to edges
- Explain why insert and lookup cost O(m) independent of the dictionary size
- Compare a trie to a hash set for autocomplete and prefix queries
A trie (pronounced “try”, from retrieval) is a tree where every node represents a single character rather than an entire key. Strings are encoded along root-to-node paths, so two words that share a prefix also share nodes.
Why Not a Hash Set?
A hash set gives O(1) average lookup for an exact key — but it cannot answer
“does any stored word start with pre?” without scanning every entry. A trie
answers prefix queries in O(m) time where m is the length of the prefix, with
zero extra work.
| Operation | Hash Set | Trie |
|---|---|---|
| Insert word | O(m) average | O(m) |
| Exact lookup | O(m) average | O(m) |
| Prefix exists? | O(n · m) | O(m) |
| All words with prefix | O(n · m) | O(m + results) |
| Worst-case insert | O(m · n) collision | O(m) |
n is the number of stored words, m is the word length. The trie wins whenever you care about prefixes.
Structure at a Glance
Each node holds a map from the next character to a child node, plus a boolean flag marking whether a complete word ends there.
root
│
c ──► {children: {a}, isEnd: false}
│
a ──► {children: {t, r}, isEnd: false}
/ \
t r ──► {children: {}, isEnd: true} ("car")
│
s ──► {children: {}, isEnd: true} ("cats")Inserting “car” and “cats” shares the nodes for c and a. Any word that
starts with “ca” traverses those two shared nodes before branching.
Complexity Summary
Let m be the length of the word being operated on.
| Operation | Time | Space |
|---|---|---|
| Insert | O(m) | O(m) new nodes worst case |
| Search | O(m) | O(1) |
| Starts-with | O(m) | O(1) |
| Delete | O(m) | O(1) amortized |
Space across the whole trie is O(A · n · m) where A is the alphabet size, but shared prefixes keep the real-world footprint far below that bound.
When to Reach for a Trie
- Autocomplete / type-ahead suggestions
- Spell checkers that need to enumerate corrections
- IP routing tables (binary trie over 32-bit addresses)
- Word games such as Boggle or crosswords
- Matching a set of patterns against a stream (Aho-Corasick builds on tries)
A sorted array of strings can answer prefix queries with binary search at O(m log n), which is competitive for read-heavy workloads. Tries shine when you both query and mutate frequently, or when you need to collect all matching words rather than just check existence.
Up Next
Build the trie node class with a children Map and an isEnd flag, then
implement insert, search, and startsWith.