March 24
Trie
What a trie means, when prefixes matter more than whole words, and why it shows up so often in dictionaries and search.
What it is
A trie is a tree-shaped structure where each edge represents one character.
The path from the root to a node represents a prefix.
Some nodes are marked as the end of a full word.
When to use it
It appears when the problem talks about:
- prefix lookup
- autocomplete
- word dictionaries
- single-character wildcard search
Common mistake
The classic mistake is treating a trie as if it always replaces Set or Map.
If you only need exact word lookup, a Set is usually simpler.
Trie becomes strong when shared prefixes actually change the search strategy.
Better question
Before using it, ask:
- do many words share relevant prefixes?
- do I need prefix lookup, autocomplete, or single-character wildcard support?
- is the extra node-and-pointer cost worth the richer search structure?
Share this page
Copy the link manually from the field below.