Lesson 274
Trie Data Structure
Prefix Trees · Fast Search
1:00How a prefix tree stores strings so that insert, search, and autocomplete each cost O(m) — independent of how many words are stored.
By the end, you can
- Explain the structural difference between a trie and a hash table, and why tries excel at prefix search.
- Describe the two fields every trie node holds and explain why each is necessary.
- Trace an insert operation, identifying which nodes are reused and which are newly created.
- Predict how many new nodes inserting a word creates, given what is already in the trie.
- Trace a search operation and determine whether it succeeds, fails due to a missing edge, or fails due to a false isEndOfWord flag.
- Describe the autocomplete algorithm (walk-to-prefix, then collect subtree) and state its cost.
- State the O(m) time complexity for insert, search, and delete, and explain why N does not appear.
- Explain the O(A · N · M) worst-case space bound and the trade-off between fixed-array and hash-map child storage.
- Compare tries and hash tables across exact lookup, prefix search, and sorted iteration.
- Define a compressed (radix) trie and explain what it compresses.
Up next in String Algorithms, Advanced DP & Competitive Techniques
