Implement Trie (Prefix Tree)
On this page
Problem statement
Build a trie (prefix tree) class with three methods:
insert(word)adds a word,search(word)returns true if that exact word was inserted, andstartsWith(prefix)returns true if any inserted word begins with the prefix. Words use lowercase English letters.
This is the "build the data structure" question behind every autocomplete and word-puzzle problem. Interviewers use it as a warm-up or as the first half of a harder question such as Word Search II. Original problem: LeetCode 208.
Example

insert("apple")
search("apple") -> true
search("app") -> false # only a prefix so far
startsWith("app") -> true
insert("app")
search("app") -> true
Constraints (assumed)
- 1 ≤ word and prefix length ≤ 2,000.
- Only lowercase letters
a–z. - Up to 30,000 calls in total.
What this question tests
- Designing a small node structure and choosing between a 26-slot array and a hash map for the children.
- Telling apart "this path exists" and "a word ends here".
- Clean class design with a shared helper instead of three copies of the same loop.
Questions to ask first
- What characters can appear? Lowercase only allows a fixed 26-slot array; Unicode needs a map.
- Will we need delete? It changes what each node stores (often a count of words passing through).
- Is memory or speed more important? Arrays are faster, maps use less memory for sparse tries.
- Should
search("")orstartsWith("")be supported? With this design,startsWith("")is true andsearch("")is false unless the empty word was inserted.
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.