Master Trie prefix tree data structures to implement ultra-fast O(L) string insertion, prefix lookup, and auto-complete search engines.
Learn how dynamic arrays achieve O(1) amortized insertion, contiguous memory layout, and geometric doubling strategies.
A Trie (pronounced "try", from retrieval) is a tree data structure specialized for storing strings where nodes share common prefix paths.
Searching for a word of length $L$ in a Trie takes $O(L)$ time, independent of how many millions of words exist in the dictionary! Furthermore, Tries find all words with a given prefix in $O(P)$ time.
(Root)
/ \
'c' 'd'
/ \
'a' 'o'
/ \ \
't'* 'r'* 'g'*
(cat) (car) (dog) * = isEndOfWord
class TrieNode {
constructor() {
this.children = {}; // Character -> TrieNode mapping
this.isEndOfWord = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let curr = this.root;
for (const char of word) {
if (!curr.children[char]) {
curr.children[char] = new TrieNode();
}
curr = curr.children[char];
}
curr.isEndOfWord = true;
}
search(word) {
let curr = this.root;
for (const char of word) {
if (!curr.children[char]) return false;
curr = curr.children[char];
}
return curr.isEndOfWord;
}
startsWith(prefix) {
let curr = this.root;
for (const char of prefix) {
if (!curr.children[char]) return false;
curr = curr.children[char];
}
return true; // Prefix path exists in Trie!
}
}
const dict = new Trie();
dict.insert("apple");
console.log(dict.search("apple")); // Output: true
console.log(dict.search("app")); // Output: false (prefix, not word)
console.log(dict.startsWith("app")); // Output: true
search("app") must verify curr.isEndOfWord === true. Checking only node existence returns true for prefixes that are not complete words.Use Tries for type-ahead search and spell checkers. Next, let's explore Graph Representations!