DSA & Algorithms
Part 2 of 16 · DSA Advanced & Company FavoritesTries / Prefix Trees
Prefix trees for autocomplete, Word Search II, and dictionary prefix queries with O(L) ops.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
The queries share prefixes
Prefer
Store the words in a trie
Each edge is one character. A node can end a word.
- search checks the end mark.
- startsWith only checks that the path exists.
- Word Search II walks the board and the trie together.
Alternative
Put every word in a hash set
Exact lookup is enough for membership, not for autocomplete or shared prefixes.
- You rescan the whole dictionary per prefix.
- You cannot prune a dead board path.
- XOR queries have no bit path to follow.
Walk one character at a time
Shared prefixes share nodes.
- 1
Start at the root
The root is not a character. - 2
Follow or create the child
One edge per character. - 3
Mark the end
search needs the mark. startsWith does not.
Overview
Prefix trees for autocomplete, Word Search II, and dictionary prefix queries with O(L) ops.
When companies ask this
Recognition cues: autocomplete, dictionary prefix, Word Search II, replace words, longest word with all prefixes, max XOR via binary trie.
Company asks: Meta Word Search II / Implement Trie; Google autocomplete-shaped; Amazon Replace Words.
Mental model
Flow
- 1
root
- nexta
- nextb
- 2
a
- nextapp end
- 3
b
- nextbat end
- 4
app end
- 5
bat end
Lesson map
Tries / Prefix Trees
Prefix trees for autocomplete, Word Search II, and dictionary prefix queries with O(L) ops.
Architecture. root Ready. a Ready. b Ready. app end Ready. bat end Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB Root["root Ready"] A["a Ready"] B["b Ready"] App["app end Ready"] Bat["bat end Ready"] Root -->|continues| A Root -->|continues| B A -->|continues| App B -->|continues| Bat
Shared prefixes share nodes; is_end marks a complete word.
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity + pitfalls
- Ops O(L); space O(total characters) with sharing.
- Pitfalls: forget
is_end; board mutate without restore; no dedupe in Word Search II; Trie vs HashSet confusion.
Interviewer traps
LeetCode drill (real problems)
- Implement Trie (Prefix Tree)
- Design Add and Search Words Data Structure
- Word Search II
- Replace Words
- Longest Word in Dictionary
- Maximum XOR of Two Numbers in an Array
- Search Suggestions System
- Map Sum Pairs
YouTube
- NeetCode - Implement Trie (Prefix Tree)
- HackerRank / Gayle - Data Structures: Tries
- William Fiset data structures playlist
Interview Q&A
Trie vs HashSet?
Answer
Exact lookup HashSet; prefixes/autocomplete Trie.
Word Search II tip?
Answer
Store the word at its end node (it may still have children); set it to null after a find to dedupe.
Complexity Word Search II?
Answer
O(RC4^L) pruned by Trie.
Binary Trie for XOR?
Answer
Path = bits MSB to LSB; prefer differing bits.
startsWith vs search?
Answer
Prefix exists vs is_end.
Array[26] vs Map?
Answer
Array for a-z speed; Map for sparse/unicode.
Delete?
Answer
Counts + remove zero-child non-end nodes.
Related wave-1?
Answer
hashing, backtracking, strings.