Design a trie (also called a prefix tree) — a structure that stores strings character by character so that lookups and prefix queries run in time proportional to the length of the key, not the number of keys stored.
The structure supports three operations:
- "insert" — add the word word to the trie. Returns null.
- "search" — return true if the exact word was previously inserted, otherwise false.
- "startsWith" — return true if any previously inserted word begins with prefix, otherwise false.
You are given the operations as two parallel arrays: operations[i] is the operation name and values[i] is its argument list ([word] for "insert"/"search", [prefix] for "startsWith"). Apply them in order and return an array holding each operation's return value (null for every "insert", a boolean for "search" and "startsWith").
For example ["insert","search","search","startsWith","insert","search"] with [["apple"],["apple"],["app"],["app"],["app"],["app"]] returns [null, true, false, true, null, true]. After inserting "apple": search("apple") is true; search("app") is false because "app" was never inserted as a complete word; startsWith("app") is true because "apple" begins with "app"; then "app" is inserted, so search("app") becomes true.
Example
search("app") is false until "app" is inserted as a full word, but startsWith("app") is true the moment "apple" exists.
Constraints
- 1 <= operations.length <= 3 * 10^4
- operations[i] is one of "insert", "search", "startsWith".
- 1 <= word.length, prefix.length <= 2000
- word and prefix consist of lowercase English letters only.
Intuition
The crude way to back a trie's three operations is to skip the tree entirely: keep a plain set of every inserted word. search is then a set membership check, and startsWith scans every stored word asking whether it begins with the prefix.
This is reframed as an op-replay function — runTrieOps(operations, values) applies each operation in order and returns one result per op (null for insert, a boolean for search / startsWith) — but the data structure inside is the real question.
function runTrieOps(operations, values) {
const words = new Set(); // every inserted word, verbatim
const result = [];
for (let i = 0; i < operations.length; i++) {
const arg = values[i][0];
if (operations[i] === "insert") {
words.add(arg); // O(L) to hash the word
result.push(null);
} else if (operations[i] === "search") {
result.push(words.has(arg)); // exact membership, O(L)
} else {
// startsWith: no shared structure, so test every stored word.
let any = false;
for (const w of words) {
if (w.startsWith(arg)) { any = true; break; }
}
result.push(any);
}
}
return result;
}search is fine, but startsWith is the weak spot: with W stored words it does O(W · L) work per query, because the set throws away the very thing the prefix question needs — the shared structure between words. Can we do better?
The key observation: words that share a prefix should share a path. Store the words as a tree where each edge is one character, so "app" and "apple" walk the same a → p → p nodes and only diverge after. Then a prefix query is a single walk down that shared path — O(L), no matter how many words are stored — and an end-of-word flag on a node distinguishes a stored word from a mere prefix. That tree is the trie itself.
There is no single-lane picture of a branching tree, so the walkthrough below traces one path through the trie — the a → p → p → l → e spine after inserting "apple" then "app" — to show how search and startsWith read the same path but disagree on the end flag. (isEnd, drawn as •, is the implementation's flag; a node with no • is a prefix only.) Walking it through:
one path after insert("apple"), insert("app") — • = end-of-word flag (isEnd)
Inserting "apple" lays down the whole a-p-p-l-e path; only the final e node is flagged as a word end.
"app" reuses the existing a-p-p prefix — no new nodes — and flags the second p as also being a word end.
Exact search follows a-p-p-l-e and finds the end flag on e — "apple" is stored.
Prefix search stops at the second p; the node exists, so some word starts with "app" — the flag is irrelevant here.
Same path, shorter: "ap" lands on the first p, which carries no flag — so "ap" is a prefix but not a stored word.
A prefix the trie never saw falls off the root immediately (no "b" edge) and returns false.
Optimization
Trie with a children map and end-of-word flag
Each trie node holds a map from a character to a child node, plus an isEnd flag marking whether a complete word terminates there. The root represents the empty prefix.
To insert a word, walk from the root one character at a time, creating any missing child, and mark the final node's isEnd. To search for an exact word, walk the same path; the word is present only if every character had a child and the final node is flagged as a word end. startsWith is the same walk but without the end check — reaching the end of the prefix is enough.
Every operation does O(L) work for a key of length L, independent of how many words are stored. We replay the operations in order, pushing null for each insert and the boolean result for each query.
function runTrieOps(operations, values) {
// A trie node: children keyed by character, plus a flag for "a word ends here".
const makeNode = () => ({ children: new Map(), isEnd: false });
const root = makeNode();
const insert = (word) => {
let node = root;
for (const ch of word) {
// Descend, creating the child path on the fly.
if (!node.children.has(ch)) node.children.set(ch, makeNode());
node = node.children.get(ch);
}
node.isEnd = true; // the last node closes a complete word
};
// Walk the path for `str`; return the node it ends on, or null if it falls off the trie.
const walk = (str) => {
let node = root;
for (const ch of str) {
if (!node.children.has(ch)) return null;
node = node.children.get(ch);
}
return node;
};
// An exact word needs the full path AND an end flag at the last node.
const search = (word) => {
const node = walk(word);
return node !== null && node.isEnd;
};
// A prefix only needs the full path to exist.
const startsWith = (prefix) => walk(prefix) !== null;
const result = [];
for (let i = 0; i < operations.length; i++) {
const op = operations[i];
const arg = values[i][0];
if (op === "insert") {
insert(arg);
result.push(null);
} else if (op === "search") {
result.push(search(arg));
} else {
result.push(startsWith(arg));
}
}
return result;
}Complexity analysis
Time complexity: O(L) per operation. Here's why:
insertwalks one node per character of the word, creating missing children as it goes —O(L)for a word of lengthL.searchandstartsWitheach follow one path of lengthL, doing O(1) work per character.
Crucially the cost is independent of how many words are stored, so over m operations whose keys total N characters the whole replay is O(N) — versus the brute force's O(W · L) per startsWith.
Space complexity: O(N). Here's why:
- The trie holds at most one node per character across all inserted words; shared prefixes collapse onto shared nodes, divergent suffixes do not.
So the structure is O(N) in the total length of the inserted words. The result array is O(m) for m operations and isn't counted against the structure.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| operations = ["search","startsWith"]values = a a | [false,false] | Queries on an empty trie — both miss. |
| operations = ["insert","search"]values = a a | [null,true] | Single insert then exact search hits. |
| operations = ["insert","search","startsWith"]values = hello hell hell | [null,false,true] | "hell" is a prefix of "hello" but not a stored word — search false, startsWith true. |
| operations = ["insert","insert","insert","search","search","startsWith"]values = a ab abc ab abx ab | [null,null,null,true,false,true] | Words that are prefixes of each other are independently searchable. |
| operations = ["insert","search","startsWith"]values = ab abc abc | [null,false,false] | A query longer than any stored word falls off the trie — both false. |
| operations = ["insert","insert","search"]values = cat cat cat | [null,null,true] | Re-inserting the same word is idempotent. |
Try it yourself
Write your solution against the real judge before checking the reference.