Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Build a tree where each node holds up to 26 child links (one per lowercase letter) plus an `isEnd` flag. `insert`, `search`, and `startsWith` all walk character-by-character from the root in O(L) time. The only difference between `search` and `startsWith` is the final check: `search` also requires the landing node's `isEnd` to be true.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can design a data structure from scratch — node shape, pointer plumbing, and the subtle isEnd flag — not just call a library. It's a 'can you build the thing, not use the thing' check.
Where candidates slip
Forgetting the isEnd flag (so `search` can't tell a full word from a mere prefix), or duplicating the walk logic across all three methods instead of factoring out a single traversal helper.
How to stand out
Factor the shared walk into one private helper, articulate that `search` = `startsWith` + `isEnd`, and note the O(L) cost is independent of the number of stored words — that's the trie's headline advantage over hashing.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachExplore the full treeCollapse the tree
How to read it:After inserting "app" and "apple". The shared a→p→p path is stored once; the double-circle node marks isEnd=true. A HashSet stores each word whole and cannot answer startsWith without scanning everything.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
HashSet of Words (Baseline — fails startsWith)
1Hint 1Explore hintHide hint
If you only had to support insert and exact search, what's the simplest structure? A hash set of the whole words.
2Hint 2Explore hintHide hint
Now try to answer startsWith with that set. There's no key for a prefix — you'd have to look at every stored word.
3Hint 3Explore hintHide hint
That last realization is the whole reason tries exist: they index by prefix, not by whole word.
A · Core idea
The most literal reading of 'store words, then look them up' is a HashSet. insert adds the word, search is a single contains call — both clean and O(L) to hash the string.
Why it looks good at first. Two of the three methods are trivial one-liners, and hashing gives average O(1) membership. If the problem stopped at insert + search, this would be the right answer and a trie would be over-engineering.
Why startsWith breaks it. A hash set keys on the whole word. There is no entry for the prefix "app", so to answer startsWith("app") you must iterate every stored word and test word.startsWith(prefix). That's O(N·L) per call — and with up to 3×10⁴ calls, it degrades to quadratic-ish behaviour. The set simply has no notion of 'words sharing a beginning'.
Why we don't ship this. The problem deliberately asks for startsWith to force a prefix-indexed structure. State this baseline to show you understand the trade, then reach for the trie that makes all three operations O(L).
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
insert("apple"); startsWith("app")Array state
scan 0
"apple".startsWith("app") → true (but we may have to check all in worst case)
true (but via a full scan, not O(L))C · Code with teaching comments
Reference implementation previewclass Trie { private Set<String> words; public Trie() { words = new HashSet<>();Explore the full codeHide the full code
D · Why it works and complexityinsert O(L), search O(L), startsWith O(N·L) timeO(N·L) spaceOpen the invariant and proofExplore the proofHide the proof
A HashSet indexes by the entire key, so it can answer 'is this exact thing present?' but never 'does anything start with this?'. The moment a prefix query appears, you need a structure that shares and indexes prefixes — that's the trie.
Complexityinsert O(L), search O(L), startsWith O(N·L) time, O(N·L) space — insert/search hash a length-L string in O(L). But startsWith has no prefix key, so it must scan all N stored words and test each → O(N·L) per call.
E · Edge cases and pitfalls4startsWith on an empty set — Loop body never runs → returns false. Correct, but the structure is still the wrong tool.Explore edge casesHide edge cases
Edge cases handled
startsWith on an empty setLoop body never runs → returns false. Correct, but the structure is still the wrong tool.
Pitfalls
- Believing search being O(1) means the design is fine — startsWith is the operation the problem is really testing.
- Using `words.contains(prefix)` for startsWith — that checks exact membership of the prefix, not whether any word begins with it.
- Shipping this in an interview without naming the O(N·L) cost — it reads as not understanding the requirement.
Approach 2 of 2 · Optimal
Trie with Children Map + isEnd Flag (Optimal)
1Hint 1Explore hintHide hint
What if words that share a prefix shared the same path through a tree, so "app" and "apple" reuse the a→p→p chain?
2Hint 2Explore hintHide hint
Give each node a map from next-character to child node, and a boolean isEnd that says 'a complete word stops here'.
3Hint 3Explore hintHide hint
insert walks/creates the path and sets isEnd at the last node. search walks and checks isEnd. startsWith walks and just checks the path existed.
A · Core idea
Model the dictionary as a tree. The root represents the empty prefix and owns no character. Each node holds a map (or 26-slot array) from a character to its child node, plus an isEnd boolean. A word is the path from the root spelling it out, with isEnd = true on the final node.
Why a tree of characters beats a set of words. Words that share a prefix share a path. "app" and "apple" both travel a→p→p; only after that do they diverge. This is exactly what makes startsWith cheap: to ask 'does any word start with app?' you just walk a→p→p and check the path exists — O(L), no scanning of other words. The set couldn't do this because it had no shared-prefix structure to walk.
Why the isEnd flag is non-negotiable. Walking the path tells you the characters exist, but not whether a word ended there. After inserting only "apple", the path a→p→p exists, so without a flag you couldn't distinguish search("app") (should be false) from search("apple") (should be true). isEnd is the one bit that separates 'a word ends here' from 'this is merely a prefix of some word'. This single flag is the entire difference between search and startsWith.
Why all three methods share one walk. insert, search, and startsWith each step through the query character by character from the root. insert creates a missing child; search and startsWith fail on a missing child. search additionally checks isEnd at the end; startsWith does not. Factoring the walk into one private helper that returns the landing node (or null) keeps the code DRY and makes the search = walk + isEnd, startsWith = walk != null symmetry obvious.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
insert("apple"); search("app"); startsWith("app"); search("apple")Interactive diagram
How insert builds shared paths
insert("apple")Inserting "app" then "apple" reuses the a→p→p chain; only "le" is new. Double-circle nodes have isEnd=true.
search("app")=false, startsWith("app")=true, search("apple")=trueC · Code with teaching comments
D · Why it works and complexityinsert O(L), search O(L), startsWith O(L) timeO(total characters inserted) spaceOpen the invariant and proofExplore the proofHide the proof
A trie is just 'a tree whose edges are characters'. Every string operation becomes a root-to-node walk. The headline win is that cost depends only on the query length L, never on how many words N you've stored — so a dictionary of a million words answers startsWith just as fast as a dictionary of ten. That O(L)-regardless-of-N property is why autocomplete and Word Search II are built on tries.
Complexityinsert O(L), search O(L), startsWith O(L) time, O(total characters inserted) space — All three operations walk exactly one character of the query at a time, doing O(1) child lookup per step, so each is O(L) where L is the query length — completely independent of N, the number of stored words. Space is the sum of all distinct character-edges, bounded by total characters inserted.
E · Edge cases and pitfalls5search("app") after insert("apple") — Walk reaches the second 'p' node, but its isEnd is false → returns false. The defining test of the isEnd flag.Explore edge casesHide edge cases
Edge cases handled
search("app") after insert("apple")Walk reaches the second 'p' node, but its isEnd is false → returns false. The defining test of the isEnd flag.startsWith("b") on a trie of only "apple"root has no 'b' child → walk returns null → false. No false positives from unrelated letters.
Pitfalls
- Omitting isEnd — then search can't distinguish a stored word from a mere prefix (search("app") wrongly returns true).
- Creating nodes during search/startsWith — only insert may mutate the tree; the read walk must return null on a missing child.
- Duplicating the traversal in all three methods instead of one walk helper — more code, more places to introduce a bug.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewclass Trie { private static class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isEnd = false; }Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1search without the isEnd check
If search only verifies that the path exists, it behaves like startsWith — returning true for any prefix of a stored word. search("app") would wrongly return true after only "apple" was inserted.
Explore the code comparisonHide the code comparison
search without the isEnd check
If search only verifies that the path exists, it behaves like startsWith — returning true for any prefix of a stored word. search("app") would wrongly return true after only "apple" was inserted.
Don't write this
public boolean search(String word) {
return walk(word) != null; // same as startsWith — WRONG
}Write this instead
public boolean search(String word) {
TrieNode node = walk(word);
return node != null && node.isEnd; // must end on a word
}2Mutating the trie during a read
Copy-pasting insert's 'create child if missing' into the walk silently inserts the query as a side effect, so a later search/startsWith for it returns true even though it was never inserted.
Explore the code comparisonHide the code comparison
Mutating the trie during a read
Copy-pasting insert's 'create child if missing' into the walk silently inserts the query as a side effect, so a later search/startsWith for it returns true even though it was never inserted.
Don't write this
def _walk(self, s):
node = self.root
for ch in s:
if ch not in node.children:
node.children[ch] = TrieNode() # side effect — corrupts the trie
node = node.children[ch]
return nodeWrite this instead
def _walk(self, s):
node = self.root
for ch in s:
if ch not in node.children:
return None # read-only: bail out, never create
node = node.children[ch]
return nodeRevise
Carry the pattern into the interview
Pattern to remember
Prefix tree (Trie) with children map + end-of-word flag
Code pattern to memorize
node = root
for ch in word:
if ch not in node.children: node.children[ch] = TrieNode()
node = node.children[ch]
node.isEnd = True # only on insert
# search: walk, return node != null AND node.isEnd
# startsWith: walk, return node != nullRules to remember
- 1Every node needs an isEnd flag — without it
search("app")wrongly succeeds when only"apple"was inserted. - 2
searchandstartsWithshare the same walk; only the last line differs (isEndcheck vs just reaching a node). - 3On a missing child during a walk, return false immediately — don't create the node (that's insert-only behaviour).
- 4Store children as a map / 26-slot array, never a list you scan — O(1) child access is the whole point.
- 5The root is empty — it represents the empty prefix and owns no character itself.
Use this pattern when
- Many strings sharing common prefixes, and you query by prefix
- Autocomplete, spell-check, dictionary, or 'words starting with X'
- Need O(L) lookup independent of how many words are stored
- A later problem layers wildcard / DFS search on top of a word set
Choose another pattern when
- Only need exact membership, no prefix queries → a HashSet is simpler and lighter
- Few words, short alphabet, one-off lookup → hashing is fine
- Keys aren't strings / sequences → a trie has nothing to branch on
- Memory is tight and words share no prefixes → trie wastes node overhead
Interview takeaway
A trie trades memory for prefix superpowers: it makes `startsWith` as cheap as `search`, which a HashSet can never do. Once you can build one from scratch, Add-and-Search-Words (wildcards) and Word Search II (grid + trie) are just DFS layered on this exact skeleton.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical Trie (Prefix Tree) design. Recognise it whenever many strings share prefixes and you query by prefix. The children-map + isEnd skeleton is the foundation for Add-and-Search-Words (wildcards) and Word Search II (trie-pruned grid DFS).
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Design Add and Search Words Data StructureSame trie, but search supports '.' wildcards — DFS that branches over all children on a dot.
- Word Search IIBuild a trie of the word list, then DFS the grid once, pruning branches that fall off the trie.
- Replace WordsInsert dictionary roots into a trie, then for each word walk until the first isEnd to find the shortest root.
- Longest Common PrefixComing soonCan be solved with a trie: insert all strings, then walk down while each node has exactly one child and isn't a word end.