Topic Lesson
Learn Trie from scratch
A complete 4-step path: handwritten notebook primer, animated visualizer, speed check quiz, and compiler practice.
What is Trie
notebook noteA trie, also called a prefix tree, is a tree structured for storing words character by character. Instead of storing entire words in individual nodes, each step down a branch represents a single letter. Words that share the same beginning, like car, card, and care, share the exact same starting path down the tree. A special boolean marker sits at the end of each valid word to show that a complete word terminates at that letter.
When to reach for it
Reach for a trie when questions involve prefix lookups, dictionary word searches, autocomplete engines, or matching prefixes against a body of text. Prompts asking whether any word in a dictionary begins with a given prefix, or searching for words on a Boggle board grid, point directly to a trie. It also applies to bitwise tasks, such as finding the maximum XOR pair among integers by treating numbers as binary prefixes.
How to think about it
Represent each trie node with an array or hash map of child links, plus a boolean flag marking if a complete word ends at that node. When inserting, start at the root and walk down character by character, creating new child nodes whenever a path does not exist yet, then mark the final node as a word ending. When searching, follow the characters; if any child link is missing, the word or prefix does not exist. If all characters match, check the boolean flag to distinguish between a full word and a partial prefix.
Operation costs
measured big-O| Operation | Time |
|---|---|
| insert word of length l into trie | O(l) |
| search for full word of length l | O(l) |
| check if any word begins with prefix of length l | O(l) |
Common mistakes to avoid
- Confusing prefix matches with full word matches by returning true when characters exist but the end-of-word flag on the final node was never set.
- Allocating fixed 26-slot arrays for child pointers without verifying that all input characters are strictly lowercase English letters.
- Forgetting to prune unvisited branches during board searches, leading to time limit exceeded errors on grids with large word sets.