DSA · Patterns, not puzzles
What is a trie and when is it useful?
Short answer
A trie is a tree of characters where each path from the root spells a prefix. Insert and lookup cost O(m) for a word of length m, and it supports prefix queries that a hash map cannot answer efficiently.
Each node represents a prefix and stores children keyed by the next character. A flag marks whether the prefix is a complete word. Shared prefixes share nodes, which saves space and makes prefix traversal natural.
class TrieNode {
constructor() {
this.children = new Map();
this.isWord = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let node = this.root;
for (const ch of word) {
if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
node = node.children.get(ch);
}
node.isWord = true;
}
search(word) {
let node = this.root;
for (const ch of word) {
if (!node.children.has(ch)) return false;
node = node.children.get(ch);
}
return node.isWord;
}
}What tries are good at
- Autocomplete and prefix suggestions
- Spell checking and dictionary lookup
- Word search on a board with backtracking
- Longest common prefix across many strings
- Bitwise tries for maximum XOR problems
A hash map gives O(1) average lookup for a full key, but it cannot enumerate all keys with a prefix without scanning. A trie can walk to the prefix node and then traverse its subtree. The trade-off is memory: each node may store a map or an array of children.
Follow-ups you should expect
Interviewers use these to check whether the first answer was understanding or memorisation.
- 1How do you implement prefix search in a trie?
- 2What are the memory trade-offs of a trie?
- 3When is a hash map better than a trie?
- 4How would you find the longest common prefix of many words?
Say it in the interview
A trie stores characters along tree edges, so each path spells a prefix and insert or search is O(m) for a word of length m. The advantage over a hash map is prefix enumeration, because I can reach the prefix node and traverse everything below it. The cost is memory for child storage, and I use tries for autocomplete, dictionaries and board word search.
Use this as a model, not a script. Saying it in your own words is what makes it survive follow-up pressure.
Related questions
Reading is step one
Now say it out loud.
Understanding an answer and delivering it under pressure are different skills. Rehearse this topic in a live DSA mock interview and get scored feedback on depth, clarity and confidence.