Coding interview pattern
Trie (Prefix Tree)
Store strings by shared prefixes for fast prefix search and word lookup.
The idea
How the trie (prefix tree) pattern works
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
When to reach for it
- You need prefix queries: does any word start with this prefix?
- You are building autocomplete or spell-check style suggestions.
- You search a board or text for many dictionary words at once.
- Exact-match plus prefix-match are both needed on the same set.
Cost
Time & space complexity
| 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
Walkthrough: Implement a Trie with insert, search, and startsWith
- 1Define a node with a map from character to child node and a boolean is-word flag.
- 2To insert, walk character by character, creating child nodes as needed, and set is-word on the final node.
- 3To search, walk the same way; return true only if you reach the end and is-word is set.
- 4To check a prefix, walk it and return true if you never fall off the trie, regardless of is-word.
- 5Every operation costs O(length of the string), independent of the dictionary size.
Translatable skeleton
The shape in pseudocode
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
Curated problem set
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
Common pitfalls
- Forgetting the is-word flag and treating every prefix as a word.
- Not pruning dead branches in Word Search II, causing a timeout.
- Heavy per-node memory from fixed-size child arrays on large alphabets.
- Mishandling the wildcard in add-and-search by not branching on every child.
In the interview
How to communicate it live
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.
Also searched as
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.
Sources
- 5.2 Tries Sedgewick and Wayne, Princeton University
- Tries (lecture slides) Sedgewick and Wayne, Princeton University
- trie NIST Dictionary of Algorithms and Data Structures
Next up
Patterns that pair well with this one
Real problems rarely match a single pattern. Interviewers like to combine this one with these.
- Sliding Window
Track a contiguous subarray or substring without re-scanning it from scratch.
- Two Pointers
Walk two indices toward or alongside each other to avoid a nested loop.
- Binary Search
Halve the search space each step over any monotonic condition, not just sorted arrays.
- Dynamic Programming
Solve overlapping subproblems once, store the results, and build the answer up.
Round out your prep
See all coding patterns, the coding questions for your role, and the behavioral round.