Unit 2.7 · about 3 h
102 / 324Tries and prefix lookup
Tries trade key storage for shared prefixes. Prefix enumeration and constrained search are awkward in hash maps and slow in sorted sets.
- implement
You can now
- Explain trie representation, prefix lookup cost and memory cost, and when a trie beats hashing.
- Implement a trie with
insert,search,startsWithand wildcard search, tested on empty strings, duplicates and shared prefixes. - Route a prefix problem to a trie, a hash map or a sorted set from its query shape.
Covers
- Trie representation, prefix lookup and memory cost
Study, in this order
1 steps
- TriesDSA Handbook - search, trees and heaps
What's in the structure; What
is_endis and is not; Choosing the children container; LC 211: wildcards and a tree-shaped walk; What it actually costsDepth · Skim LC 212 (the trie as prune oracle) and Pattern variants worth knowing for recognition; only LC 208 and 211 are implemented here.
Focus on
searchchecksis_end;startsWithdoes not. After insertingcarandcard, the node forcaris terminal and still has adchild: terminal and leaf are orthogonal.- Lookup costs \(O(L)\) in the key length with one step per character, the same factor a hash pays to read the key. The trie wins on prefix queries (list every word under
ca), which hashing cannot enumerate without scanning the table. - The children container sets the constants: a 26-array is \(O(1)\) per step but wastes nulls (the chapter estimates about 20 MB per 100k nodes);
dictchildren handle Unicode and sparse alphabets. - Wildcard
'.'tries every non-null child by DFS. LC 211 allows at most 2 dots, so the fan-out caps at \(26^2 = 676\) paths; with many dots, scanning the stored words of the query's length is the simpler bound.
Reproduce closed-book
dict children. Insert apple and app; assert search(app) is True, search(appl) is False and startsWith(app) is True. Add wildcard search; assert wildcard('.pp') is True and wildcard('b..') is False. Differential-test search and startsWith against a Python set oracle on random word lists including empty strings and duplicates.Traps
- Pasting
searchintostartsWith. The shared walk must skip theis_endcheck for prefix queries. - Sizing the children array for lowercase only, then indexing
ord('A') - ord('a') = -32. Dict children or explicit alphabet checks avoid the silent negative index. - Running one DFS per word on a board instead of one DFS guided by the trie. The trie prunes every word sharing an impossible prefix at once.
Practice
LeetCode 208: Implement Trie (Prefix Tree)
Trie with insert, search and startsWith over lowercase words; example sequence in the problem statement
Test the empty string, duplicate inserts and the car/card shared-prefix case. After submitting, read the AlgoMaster write-up for Implement Trie (https://algomaster.io/learn/dsa/implement-trie-prefix-tree).
LeetCode 211: Design Add and Search Words Data Structure
Wildcard '.' search over the same trie; the dot matches any single letter
Implement the dot as DFS over non-null children. After submitting, read the AlgoMaster write-up for Design Add and Search Words Data Structure (https://algomaster.io/learn/dsa/design-add-and-search-words-data-structure).
Self-test
-
After inserting
carandcard, is the node forcara leaf? Is it terminal?Terminal but not a leaf:is_endisTrueand it still has thedchild. The two flags are independent. -
Why can a hash map not answer 'list every word starting with ca' efficiently?
Hashes destroy prefix locality: matching words scatter across buckets, so enumeration scans the whole table. A trie walks tocaonce, then enumerates only that subtree. -
What is the worst-case cost of wildcard search with \(k\) dots over alphabet size \(R\)?
\(O(R^k)\) trie paths, since each dot fans out to every non-null child. LC 211 stays feasible by capping queries at 2 dots (\(26^2 = 676\)). With many dots, grouping words by length and scanning the group costs \(O(N L)\) for \(N\) words of length \(L\) and is the safer bound. -
When does a sorted set beat a trie for prefix queries?
On memory and simplicity for a single range: bisecting'ca'to'cb'answers one prefix query with no per-node overhead. Tries win when many prefix walks share structure or when per-character steps with wildcards are needed.
Completion criterion
Stop when
Insert, search, startsWith and wildcard search match a set oracle on random word lists with empties and duplicates, and you can defend trie versus hash map versus sorted set for a new prefix task.
Leads to
- 4.1 Recursion contracts, backtracking and sound pruning Wildcard search is depth-first search over trie children; that unit owns the general backtracking form.
- 5.4 Sequence and string dynamic programming Prefix structure reappears in string dynamic programming.
Comes after
- 2.5 Binary search trees, balance and augmented treesTries serve prefix workloads where key order is irrelevant.
Resources for this unit
- DSA Handbook - search, trees and heaps Study Part 2 Search and Sort, Part 5 Linked Lists, and Part 6 Trees and Heaps. Include canonical and answer-space binary search, comparison and linear-time sorts, quickselect, sentinels, cycles, heaps, BSTs, balanced-tree vocabulary, tries and segment trees.
Also in this section
- AlgoMaster DSA - ordered structures slice Attempt Koko Eating Bananas, Validate Binary Search Tree and Find Median from Data Stream cold. Use Merge Intervals only if interval modeling remains weak, and include duplicate-heavy and skewed inputs.
- Algorithmica - search and sorting performance Use the binary-search, sorting, branch prediction and cache chapters to explain why two algorithms with the same asymptotic bound cross over on real workloads.
- Algorithms Use Chapter 1 (mergesort, quicksort, recursion trees and linear-time selection) when deriving merge, partition and selection algorithms, and lecture note 12 Lower Bounds for the comparison-sorting decision-tree argument. This is the proof reference when the handbook explanation is too brief.
- NeetCode - unseen ordered problems Use one unseen tree problem and one heap or interval problem as the final transfer check, with solution material closed until submission.
- DSA Handbook Patterns - quicksort vs mergesort vs heapsort Use The decision, Algorithms compared and Side-by-side to pick a comparison sort from the binding constraint; problem details stay with their units.
- DSA Handbook Patterns - quickselect vs heap for top-K Use The decision through Side-by-side for the streaming, sorted-output and mutation routing; problem details stay with their units.
- DSA Handbook Patterns - two-heap median archetypes Use Streaming median and Variants side-by-side for the two-heap invariants; skip sliding-window median and sketches.
- DSA Handbook Patterns - merge intervals archetypes Use The decision, Variants and the LC 56 and LC 57 signature problems for merge and insert implementation, and the Meeting Rooms II archetype for the min-heap form.
- DSA Handbook Patterns - sweep line archetypes Use The decision and the 1D event sweep variant for
+1/-1concurrency counting with explicit tie-breaks; skyline and rectangle area are recognition only.