Implement Trie (Prefix Tree)
A trie is a tree where every edge is a single letter, so a word is spelled out by walking from the top of the tree down one letter at a time. Words that start the same way share the same path, which is why it is also called a prefix tree. Build a trie that supports three actions: insert(word) stores a word, search(word) says whether that exact word was stored, and startsWith(prefix) says whether any stored word begins with that prefix. Because a class cannot be written down as plain data, this exercise uses the usual interview convention for design questions: you are handed a list of operation names and a matching list of argument lists, and you return the list of results. The first operation is always the constructor name and its result is null. insert also returns null, because it only stores something. search and startsWith return true or false.
Constraints
- 1 ≤ word.length, prefix.length ≤ 2000
- word and prefix consist only of lowercase English letters
- At most 3 × 104 calls in total to insert, search and startsWith
Example
operations = ["Trie", "insert", "search", "search", "startsWith", "insert", "search"], args = [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]][null, null, true, false, true, null, true]Explanation After inserting "apple", searching for "apple" is true but searching for "app" is false, because no word ends at "app" yet. startsWith("app") is still true, because "apple" begins with it. After inserting "app" as well, searching for "app" becomes true.
In plain terms
- Trie
- A tree of letters. Each node holds links to the next possible letters, so following a path from the top spells out a stored word or the beginning of one.
- Prefix
- The beginning of a word. "app" is a prefix of "apple". Every word is also a prefix of itself.
- End-of-word marker
- A true/false flag on a node saying "a complete word finishes right here". Without it you could not tell "app" (a stored word) apart from "app" (only the start of "apple").
- Node
- One spot in the tree. Each node remembers which letters can come next and whether a word ends at it.
Walking the letters of "cat" down the trie
The trie starts as a single empty root node with no letters under it.
What happens in this step
trie = new Trie()
root exists, root.children = {}
root.isEnd = false
The root spells the empty string. Every stored word is a path that starts here.Steps to visualize
- The row of cells is one path through the trie: the root, then one cell per letter of the word being walked.
- Each cell shows what that node looks like — "new" means the node was just created, "node" means it already existed, "end" means a complete word finishes there.
- Inserting walks down the letters and creates any node that is missing, then marks the last one as an end of word.
- Searching walks the same path but creates nothing — it fails the moment a letter is missing, and at the end it also checks the end-of-word marker.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
The trie starts as a single empty root node with no letters under it.
What happens in this step
trie = new Trie()
root exists, root.children = {}
root.isEnd = false
The root spells the empty string. Every stored word is a path that starts here.Solution
function runTrieOperations(operations, args) {
class TrieNode {
constructor() {
this.children = {};
this.isEnd = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let node = this.root;
for (const ch of word) {
if (!node.children[ch]) {
node.children[ch] = new TrieNode();
}
node = node.children[ch];
}
node.isEnd = true;
return null;
}
walk(prefix) {
let node = this.root;
for (const ch of prefix) {
if (!node.children[ch]) {
return null;
}
node = node.children[ch];
}
return node;
}
search(word) {
const node = this.walk(word);
return node !== null && node.isEnd;
}
startsWith(prefix) {
return this.walk(prefix) !== null;
}
}
const results = [];
let trie = null;
for (let i = 0; i < operations.length; i++) {
const name = operations[i];
const arg = args[i][0];
if (name === 'Trie') {
trie = new Trie();
results.push(null);
} else if (name === 'insert') {
results.push(trie.insert(arg));
} else if (name === 'search') {
results.push(trie.search(arg));
} else {
results.push(trie.startsWith(arg));
}
}
return results;
}- Time
- O(L) per operation, where L is the length of the word or prefix
- Space
- O(total letters inserted)
Test cases
| Input | Expected | Covers |
|---|---|---|
operations = ["Trie", "insert", "search", "search", "startsWith", "insert", "search"], args = [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]] | [null, null, true, false, true, null, true] | example from the docstring |
operations = ["Trie", "search", "startsWith"], args = [[], ["a"], ["a"]] | [null, false, false] | nothing was inserted, so every lookup fails |
operations = ["Trie"], args = [[]] | [null] | smallest possible input, just the constructor |
operations = ["Trie", "insert", "insert", "search"], args = [[], ["a"], ["a"], ["a"]] | [null, null, null, true] | inserting the same word twice is harmless |
operations = ["Trie", "insert", "startsWith"], args = [[], ["ab"], ["abc"]] | [null, null, false] | a prefix that runs past the end of every stored word |
operations = ["Trie", "insert", "insert", "insert", "search", "search", "startsWith", "startsWith"], args = [[], ["car"], ["card"], ["care"], ["car"], ["ca"], ["care"], ["cat"]] | [null, null, null, null, true, false, true, false] | several words sharing a prefix, mixing searches and prefix checks |