{ } TreeIntermediate interactive
Trie (Prefix Tree)
Shared-prefix tree for fast string lookup.
trie
7 chars
r
t
a
c
g
o
d
•
word end
A path from the root spells a prefix. Lookup is O(word length).
How it works
A trie stores strings character-by-character along tree edges, so words with shared prefixes share a path. Lookup and insert cost O(L) in the word's length — independent of how many words are stored — making it the engine behind autocomplete and spell-check.
Mental models
- A path from the root spells a prefix; a flagged node ends a word.
- Lookup time depends on the word, not the dictionary size.
Complexity
- Insert
- O(L)L = word length
- Search
- O(L)
- Prefix query
- O(P)P = prefix length
- Space
- O(N·Σ)nodes × alphabet
Reach for it when
- Autocomplete & typeahead
- Spell checkers
- IP routing tables