When to use it#
Look for the structural evidence below before naming the pattern. The constraints and invariant - not a keyword - make the choice defensible.
Recognition signals
- Prefix search
- Dictionary branching
When another approach fits better
- Only exact membership is required
- The alphabet/volume makes node overhead unjustified compared with sorting or hashing
How it works#
Scan every stored word for each prefix query.
Choose map-backed or fixed-alphabet child storage from explicit constraints.
Create or follow one edge per character.
Set and check a terminal marker separately from path existence.
InvariantA path from root spells a prefix present in inserted keys; a terminal marker distinguishes a complete key from a prefix only.
Example and template#
Implement Trie (Prefix Tree)
Distinguish a complete word from a reachable prefix.
Open the full problem brief- Insert cat
root → c → a → t*The star marks a complete stored word.
- Query ca
root → c → aThe path proves a prefix, not a complete word without terminal state.
insert(word):
node = root
for char in word:
node = node.children.get_or_create(char)
node.terminal = true
search(word):
node = walk characters or fail
return node.terminal- Time
- O(L) per insert/search/prefix query
- Space
- O(total inserted characters) worst case
- Assumptions
- L is query length; child lookup cost depends on map or fixed alphabet representation.
Pitfalls#
Common wrong approaches
The structure cannot distinguish a stored word from a prefix of another word.
It may multiply memory when the character domain is sparse or broad.
Edge cases
- Empty string policy
- Prefix is also a word
- Unicode normalization
- Duplicate insertion
Interview narration
- “The required operation is prefix traversal, so a hash set alone is insufficient.”
- “Each node represents a prefix, not a word.”
- “The terminal flag is the separate whole-word contract.”
Practice#
Implement Trie (Prefix Tree)
Distinguish a complete word from a reachable prefix.
Practice this problemSuggest dictionary entries after each typed prefix.
Reveal the pattern decision
A trie can share prefix traversal; ranking suggestions still needs additional per-node metadata.
Transfer problem
Support wildcard word lookup where one character may match any child.
Checkpoint: Walk ordinary characters directly and branch only at wildcard positions, with terminal-state checking at the end.
Follow-up variations
- Store top suggestions per prefix
- Compress unary paths and discuss update complexity
Error-log prompts
- Did path existence get confused with whole-word existence?
- Was the alphabet/memory trade-off explicit?