Algorithms / Tries Prefix Search
Least You Need to Know: Tries, Prefix Search, and Shared Prefix Structure
A trie stores strings by characters along root-to-node paths. It is useful when many words share prefixes and the interview task asks about prefix lookup, autocomplete, or word-search branching.
Least you need to know
- Each edge in a trie represents one character choice, and each node corresponds to a prefix.
- Shared prefixes are stored once, which is why tries are good for prefix-heavy workloads.
- A terminal marker distinguishes a full stored word from a prefix that is only part of a longer word.
- Searching for a prefix follows one character at a time; failure happens as soon as a needed edge is missing.
- Tries trade extra pointer-heavy structure for predictable prefix operations.
Key notation
- root — empty-prefix start node
- terminal / end-of-word — marker that a full dictionary word ends here
- path label — string formed by characters along a root-to-node path
Worked example
- Insert
to,tea, andten. - The root has a
tedge, then a sharedeedge forteaandten, whiletobranches at the second character. - The node for path
teis a prefix node, not yet a complete word unless a terminal marker is also present. - This is why prefix lookup can reuse structure instead of scanning every word separately.
Common mistakes
- Students often forget that a prefix node and a complete word are different unless a terminal marker is set.
- Students may think each node stores a whole substring; it really stores position in a prefix tree.
- Students sometimes choose tries when only exact membership of a few words is needed and a hash set would be simpler.
How to recognize it
- If the prompt asks for many prefix queries or autocomplete behavior, think trie.
- If many candidate strings share long common prefixes, a trie may compress repeated traversal work.
- If the task branches by characters one step at a time, a prefix tree is often the right abstraction.
Next recommended lesson
Continue through this topic with Least You Need to Know: Read/Write Pointers, Compaction, and Deduping.
Least You Need to Know: Read/Write Pointers, Compaction, and DedupingRelated lessons
Keep going with nearby lessons in the same topic.