Coding interview pattern
Store strings by shared prefixes for fast prefix search and word lookup.
The idea
A trie is a tree where each edge is labelled with a character and each path from the root spells a prefix. Words sharing a prefix share the same path until they diverge, which makes the trie the natural structure for prefix queries: checking whether any stored word starts with a given prefix is O(length of prefix), independent of how many words are stored. A boolean flag on a node marks the end of a complete word.
Tries beat hash sets whenever the query is about prefixes rather than exact membership: autocomplete, spell-check suggestions, and any starts-with search. They also enable elegant solutions to multi-word search problems, like finding all dictionary words present on a board (Word Search II), where you walk the board and the trie in lockstep and prune branches the moment no word continues down that path.
The cost is memory: a node per distinct character along every prefix, which can be large for big alphabets or many long words. Implementations trade off a fixed-size child array (fast, memory-heavy) against a hash map of children (compact, slightly slower). In interviews, a small TrieNode class with a children map and an is-word flag, plus insert and search and startsWith methods, is the expected fluency.
Recognition
Cost
| Operation | Time | Space |
|---|---|---|
| Insert a word | O(L) | O(L) new nodes |
| Search / startsWith | O(L) | O(1) |
| Total storage | - | O(total characters) |
Worked example
Translatable skeleton
Language-agnostic on purpose. Translate it to your language of choice.
class Node: children = {}; is_word = False // insert/search walk children char by char; startsWith ignores is_wordPractice
Work these in order, easy to hard. Each is chosen to drill a different facet of the pattern.
| Problem | Level | Why it fits |
|---|---|---|
| Implement Trie (Prefix Tree) | Medium | The structural template. |
| Design Add and Search Words Data Structure | Medium | Trie with a wildcard, DFS on '.'. |
| Word Search II | Hard | Walk the board and trie together; prune dead branches. |
| Replace Words | Medium | Find the shortest stored root prefix. |
| Longest Word in Dictionary | Medium | Words buildable one letter at a time. |
| Maximum XOR of Two Numbers | Medium | Binary trie over the bits. |
Avoid these
In the interview
Recognising the pattern is half the score; saying the right things out loud is the other half. These are the sentences that earn the signal.
Justify the trie over a hash set by naming the operation, prefix or starts-with queries, since a hash set answers exact membership but cannot answer prefix questions efficiently.
Sketch the node shape first, a children map plus an is-word flag, and state that every operation costs O(length of the string) independent of the dictionary size; that bound is the selling point.
For board-search problems like Word Search II, explain that you walk the board and the trie together and prune the moment no word continues, which is what makes it tractable.
prefix tree - trie autocomplete - word dictionary trie
Last reviewed by the site editor: June 2026
An external resource we recommend. AlgoExpert is not affiliated with us and we earn nothing from this link.
Next up
Real problems rarely match a single pattern. Interviewers like to combine this one with these.
Track a contiguous subarray or substring without re-scanning it from scratch.
Walk two indices toward or alongside each other to avoid a nested loop.
Halve the search space each step over any monotonic condition, not just sorted arrays.
Solve overlapping subproblems once, store the results, and build the answer up.
See all coding patterns, the coding questions for your role, and the behavioral round.