Implement Trie (Prefix Tree)
The Prompt
A trie (pronounced "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. Implement the Trie class: `Trie()` initializes the trie object. `insert(word)` inserts the string `word` into the trie. `search(word)` returns `true` if the string `word` is in the trie. `startsWith(prefix)` returns `true` if there is a previously inserted string `word` that has the prefix `prefix`.
Understanding the Problem
A trie stores strings the way a filing system stores paths: one node per character, and words that share a prefix share the exact same nodes. Each node holds a map from character to child node plus a boolean flag marking "a complete word ends here". The root is empty — it represents the zero-length prefix of everything.
All three operations are the same walk. insert creates missing child nodes as it descends and flags the last one; search walks the path and demands the end flag be set; startsWith walks the path and is satisfied just by arriving. The only difference between search and startsWith is that final flag check.
The Interview Flow
Interviewer
Let's talk about implementing a Trie. What is the basic structure?
Candidate
A trie is made of nodes. Each node represents a character. A common way to implement a node is with a hash map to store its children (mapping a character to another TrieNode) and a boolean flag to mark if the node represents the end of a complete word.
Interviewer
How does the `insert` operation work?
Candidate
To insert a word, I start at the root of the trie. For each character in the word, I check if the current node has a child corresponding to that character. If not, I create a new TrieNode and add it to the children map. Then, I move my pointer to that child node. After processing all characters, I mark the final node's "end of word" flag as true.
Interviewer
And how does `search` differ from `startsWith`?
Candidate
They are very similar. Both traverse the trie based on the characters of the input string or prefix. The `startsWith` method just needs to successfully traverse the entire prefix; if it can do that, it returns true. The `search` method needs to do the same, but with one extra condition: after traversing, the final node's "end of word" flag must be true. This distinguishes a prefix from a complete, inserted word.
Interviewer
That's a very clear explanation of all the core operations. Please go ahead and implement the Trie class.
Why does sharing prefixes make every operation O(L)?
The invariant: after any sequence of inserts, the path root → c1 → c2 → ... → ck exists if and only if some inserted word starts with c1c2...ck, and the node at the end of a path is flagged if and only if that exact word was inserted. Insert preserves it by building the missing suffix of the path; queries just read it.
Because each step consumes exactly one character, every operation costs O(L) where L is the word length — independent of how many words are stored. The trade is space: O(total characters inserted) nodes in the worst case, less whenever words overlap on a prefix.
Node-based Implementation
- **1. Define the TrieNode Class:**
- - It should contain a `children` map (e.g., character to TrieNode).
- - It should have a boolean `isEndOfWord`.
- **2. Implement the Trie Class:**
- - The constructor initializes a `root` TrieNode.
- - **`insert(word)`:**
- - Start with `curr = root`.
- - For each `char` in `word`, check if `char` is in `curr.children`.
- - If not, create a new `TrieNode` and add it: `curr.children[char] = new TrieNode()`.
- - Move to the next node: `curr = curr.children[char]`.
- - After the loop, set `curr.isEndOfWord = true`.
- - **`search(word)`:**
- - Start with `curr = root`.
- - Traverse the trie as in `insert`. If at any point a character is not found in the children map, return `false`.
- - After the loop, return `curr.isEndOfWord`.
- - **`startsWith(prefix)`:**
- - Start with `curr = root`.
- - Traverse the trie as in `insert`. If at any point a character is not found, return `false`.
- - If the loop completes, it means the prefix exists. Return `true`.
Try it yourself
Write your solution and run it against 1 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
class TrieNode {
constructor() {
this.children = {};
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;
}
}Explanation
Insert "app" and then "apple", and watch the second insert reuse the first one's path.
1insert("app"): starting at the root, each character gets a node — a, then p, then p. The last node is flagged as a word end, which is what makes "app" a stored word rather than just a path.
2insert("apple"): the walk reuses the existing a → p → p nodes (✓) without creating anything, then adds only l and e. Two words, one shared prefix path — this is the space saving tries buy.
3Queries: search("app") walks 3 steps and finds the end flag — true. startsWith("app") is true for the same path without needing the flag. search("appl") is false: the path exists but l has no end flag.
Complexity Analysis
TIME
O(L) for all ops
SPACE
O(N*L)
Finished working through this one?
Mark it complete to track it on your Data Structures path.