208. Implement Trie (Prefix Tree)
mediumAsked at ShopifyShopify uses Trie design to test whether you know when to reach for prefix trees vs hash maps. Product autocomplete, tag suggestions, and discount-code prefix lookup are all real motivations.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Shopify loops.
- Glassdoor (2026-Q1)— Shopify Backend Developer + Engineering Lead onsites cite Trie as a data-structure design round with autocomplete as the typical follow-up.
- Reddit r/cscareerquestions (2025-12)— Shopify new-grad interview reports include Trie with a product-search follow-up.
Problem
A trie (pronounced as '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: insert(word), search(word) returns true if word is in the trie, and startsWith(prefix) returns true if there's any word with that prefix.
Constraints
1 <= word.length, prefix.length <= 2000word and prefix consist only of lowercase English letters.At most 3 * 10^4 calls in total to insert, search, and startsWith.
Examples
Example 1
insert("apple"); search("apple"); search("app"); startsWith("app"); insert("app"); search("app")[null,null,true,false,true,null,true]Approaches
1. HashSet of all words (no trie at all)
Store every inserted word in a Set. search is O(1). startsWith requires iterating every word.
- Time
- O(1) search, O(n * L) startsWith
- Space
- O(n * L)
class TrieSet {
constructor() { this.words = new Set(); }
insert(word) { this.words.add(word); }
search(word) { return this.words.has(word); }
startsWith(prefix) {
for (const w of this.words) if (w.startsWith(prefix)) return true;
return false;
}
}Tradeoff: Fast search but startsWith is linear in word count — defeats the point. Mention only to motivate the trie.
2. Trie with object children (canonical)
Each node holds a children map (or 26-array) and an isEnd flag. Walk char by char on every operation.
- Time
- O(L) per op where L is word length
- Space
- O(N * L) for N words
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;
}
_traverse(s) {
let node = this.root;
for (const ch of s) {
if (!node.children[ch]) return null;
node = node.children[ch];
}
return node;
}
search(word) {
const node = this._traverse(word);
return node !== null && node.isEnd;
}
startsWith(prefix) {
return this._traverse(prefix) !== null;
}
}Tradeoff: Object children give cleaner code and Unicode support. The textbook answer. O(L) per operation where L is the word length, independent of how many words are stored.
3. Trie with 26-element array (slightly faster constant factor)
Replace the children object with a length-26 array indexed by (char - 'a'). Tiny perf win for the lowercase-English constraint.
- Time
- O(L) per op
- Space
- O(26 * N * L)
class TrieNode26 {
constructor() {
this.children = new Array(26).fill(null);
this.isEnd = false;
}
}
class TrieArray {
constructor() { this.root = new TrieNode26(); }
insert(word) {
let node = this.root;
for (const ch of word) {
const idx = ch.charCodeAt(0) - 97;
if (!node.children[idx]) node.children[idx] = new TrieNode26();
node = node.children[idx];
}
node.isEnd = true;
}
_traverse(s) {
let node = this.root;
for (const ch of s) {
const idx = ch.charCodeAt(0) - 97;
if (!node.children[idx]) return null;
node = node.children[idx];
}
return node;
}
search(word) {
const node = this._traverse(word);
return node !== null && node.isEnd;
}
startsWith(prefix) { return this._traverse(prefix) !== null; }
}Tradeoff: Array indexing is slightly faster than object property lookup in V8. Sacrifices ease of Unicode extension. Bring it up only if the interviewer wants to discuss micro-optimizations.
Shopify-specific tips
Shopify's expected follow-up: 'add an autocomplete method that returns the top K words with a given prefix'. Be ready to discuss DFS from the prefix node with a heap of (frequency, word). Senior candidates also get 'serialize this trie for disk persistence' — the answer is DFS preorder with a sentinel for null children.
Common mistakes
- Conflating search and startsWith — search requires the final node's isEnd to be true; startsWith only requires the node to exist.
- Forgetting to set isEnd = true at the end of insert.
- Using a single shared 'children' map at the root level instead of per-node (collapses the entire trie into one map).
- Iterating with index instead of for..of, then mishandling Unicode characters that are surrogate pairs.
Follow-up questions
An interviewer at Shopify may pivot to one of these next:
- Add a delete(word) method.
- Autocomplete — return all words with a given prefix.
- Top-K autocomplete with frequencies.
- Word Search II (LeetCode 212) — trie + DFS on a board.
- Persist the trie to disk; reload efficiently.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
When is a Trie strictly better than a hash set?
When you need prefix operations: longest common prefix, autocomplete, prefix counts. Hash sets give O(1) exact-match but O(n) prefix scans. For pure exact-match-only workloads, hash sets win.
Object children vs array children — which to ship?
Object for readability and Unicode safety. Array for measured perf gains when the alphabet is constrained. Default to object in interviews; mention the array variant if asked about micro-perf.
Free learning resources
Curated free links for this problem.
Practice these live with InterviewChamp.AI
Drill Implement Trie (Prefix Tree) and other Shopify interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →