← Back to the trees page
Trie (Prefix Tree)
A tree keyed by characters: one path per prefix. Lookup cost depends on key length, not on how many keys are stored.
What to know
- Each node holds children (map or 26-array) plus an end-of-word flag.
- Autocomplete = walk to the prefix node, then DFS the subtree.
- Word Search II pairs a trie with grid DFS to prune dead branches early.
In the wild: Search-box autocomplete, spell checkers, IP routing (radix tries), T9 input.
Algorithms to reach for
Insert / search / startsWith
O(L)Prefix dictionary ops (LeetCode 208)
Wildcard search with DFS
O(26^dots · L)Match "." patterns (LeetCode 211)
Trie + grid DFS
prunes hardFind many words in a letter grid (LeetCode 212)
Practice problems — with full guides
Each problem has its own page: progressive hints, how to approach it, and the full solution.