Why This Matters
Tries make prefix structure explicit. They are useful for autocomplete, spell checking, routing tables, token prefix matching, word dictionaries, and word-search pruning with backtracking.
The invariant is that the path from the root to a node spells the prefix represented by that node.
Prerequisite Check
Review Trees and Hash tables. A common implementation uses a dictionary from character to child node at each tree node.
Learning Objectives
By the end, you should be able to:
- Explain the difference between prefix match and whole-word match.
- Implement insert, search, and starts-with operations.
- Analyze trie cost in terms of string length.
- Connect tries to backtracking word-search pruning.
- Decide when a trie is overkill compared with a hash set.
Core Idea
Each edge stores one character. Shared prefixes share the same path; terminal markers distinguish full words from mere prefixes.
| Pattern | Invariant | Typical problem |
|---|---|---|
| Word insert | path exists for every character | dictionary build |
| Whole-word search | terminal marker is true at last node | exact lookup |
| Prefix search | path exists regardless of terminal marker | autocomplete |
| Trie + DFS | current grid path exists in trie | word search pruning |
Visual Model
root
└─ c
├─ a ─ t*
└─ o ─ d ─ e*
* marks a complete stored word.
ca is a prefix but not a word unless its node is marked terminal.
Non-Example or Failure Mode
A trie is not always better than a hash set. If you only need exact membership and never query prefixes, a hash set is simpler and often faster in practice.
Worked Example
Insert "cat" and "code".
cat creates c -> a -> t and marks t terminal.
code reuses c, then creates o -> d -> e and marks e terminal.
search("ca") is false unless ca was inserted.
starts_with("ca") is true.
LeetCode-Style Problem Patterns
| Pattern | Recognition signal | Move |
|---|---|---|
| Implement Trie | explicit insert/search/prefix operations | node with children and terminal flag |
| Word search II | many dictionary words on a grid | trie pruning plus backtracking |
| Replace words | choose shortest dictionary prefix | walk trie until terminal |
| Autocomplete | return completions for a prefix | descend to prefix node then DFS |
Common Mistakes
| Mistake | Correction |
|---|---|
| Treating every prefix as a word. | Use an explicit terminal marker. |
| Copying strings at every node. | Store structure; reconstruct only when needed. |
| Forgetting empty-string behavior. | Decide whether empty strings are allowed. |
| Using trie when exact hash lookup is enough. | Use the simpler data structure when prefixes do not matter. |
Diagnostic Questions
| Question type | Question | Answer signal |
|---|---|---|
| Definition | What does a trie path represent? | The prefix spelled by edge labels from root to that node. |
| Example / non-example | If "cat" is stored, is "ca" automatically a word? | No; it is only a prefix unless marked terminal. |
| Computation | What is lookup time for a word of length L? | O(L) dictionary-child lookups. |
| Proof | Why does prefix search stop after walking the prefix? | The invariant says all descendants share that prefix. |
| Transfer | Why do tries help word-search backtracking? | Branches not matching any dictionary prefix can be pruned immediately. |
Exercises
Beginner:
- Insert three words into a trie by hand.
- Decide which prefixes are terminal words.
- Implement
starts_with.
Intermediate:
- Return all words with a given prefix.
- Use a trie to replace words with their shortest dictionary root.
Challenge:
- Combine trie lookup with grid backtracking to find dictionary words without exploring impossible prefixes.
Diagram Recommendation
Type: prefix-tree diagram.
Caption: "Shared prefixes reuse the same path; terminal markers decide whole words."
Purpose: Separate exact membership from prefix existence.
Implementation Task
Implement a small trie with insert, search, and starts_with. Test prefix-only cases.
Run trie operations
This cell implements insert, exact search, and prefix search with terminal markers.
Output will appear here.
Next Topics
References
- Princeton Algorithms, Tries: https://algs4.cs.princeton.edu/52trie/
- MIT OpenCourseWare. 6.006 Introduction to Algorithms, Spring 2020: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
- Python documentation, dictionary type: https://docs.python.org/3/library/stdtypes.html#mapping-types-dict