Quick Overview
A trie spends one node per character, so lookup costs `O(L)` in the length of the word and never depends on how many words are stored. That is what makes prefix search cheap where a hash set cannot help.
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!
Big O describes how work grows, not how long it takes. An `O(N^2)` algorithm on 1,000 items does a million steps; the same work at `O(N log N)` does about 10,000.
A dynamic array doubles rather than growing by one, so the expensive copy lands on the 1st, 2nd, 4th and 8th push. Averaged across every push, that is `O(1)` amortised.
A nested loop tests every pair in `O(N^2)`. On sorted data, moving two pointers inward from both ends rules out half the remaining candidates at each step and settles it in one `O(N)` pass.