Intermediate LevelData Structures & Algorithms
What is a Trie (Prefix Tree) and what are its advantages over a hash map for strings?
ā Interview Prompt: Explain Trie data structure, O(L) insert/search, prefix queries, autocomplete use cases, and space trade-offs vs a hash map.
A Trie (retrieval tree / prefix tree) is a tree where each node represents a character, and paths from root to leaf nodes spell out keys.
Operations: $O(L)$ where $L$ = key length
ā¢
Insert/Search: Traverse one character at a time from root.
ā¢
Prefix Query: Check if any word starts with a given prefix in $O(P)$ where $P$ = prefix length.
Advantages over Hash Map:
ā¢
Efficient prefix searches and autocomplete ā hash maps can't answer "all words starting with 'un'" efficiently.
ā¢
Shared prefix storage saves space for large dictionaries.
ā¢
Lexicographic order inherently supported.
Code Implementation Example
typescript
class TrieNode {
children = new Map<string, TrieNode>();
isEnd = false;
}
class Trie {
root = new TrieNode();
insert(word: string): void {
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.isEnd = true;
}
search(word: string): boolean {
let node = this.root;
for (const ch of word) {
if (!node.children.has(ch)) return false;
node = node.children.get(ch)!;
}
return node.isEnd;
}
startsWith(prefix: string): boolean {
let node = this.root;
for (const ch of prefix) {
if (!node.children.has(ch)) return false;
node = node.children.get(ch)!;
}
return true; // any word with this prefix exists
}
}š”Trie implementation with O(L) insert, search, and prefix query.
šÆ Interview Key Takeaway
Tries provide O(L) prefix queries ā perfect for autocomplete, spell checkers, and IP routing tables. Hash maps lack prefix semantics.
#DSA#Trie#Prefix Tree#Strings#Intermediate
Back to all Data Structures & Algorithms Questionsā