Practice Implement Trie (Prefix Tree)
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Problem Statement
Implement Trie(), insert(word), search(word), and startsWith(prefix). insert stores a word. search is true only for a complete word previously inserted; startsWith is true when at least one stored word begins with the supplied prefix. All inputs contain lowercase English letters. Practice approach: Follow one edge per character, creating nodes during insertion. Mark the terminal node as a complete word. Prefix search only requires the path to exist, while exact search also requires that terminal marker. Each operation takes O(L) time for its argument length.
Source: Implement Trie (Prefix Tree) on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
Trie(); insert("car"); search("ca"); startsWith("ca"); search("car")[null,null,false,true,true]
The prefix ca exists as a path but is not a stored complete word.
Constraints
How to solve Implement Trie (Prefix Tree)
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
Words sharing a prefix share the same path from the root, so the trie stores each distinct prefix once. The only information beyond the path is a per-node flag marking where a complete word ends, which is what separates search from startsWith.
Why brute force is not enough
A hash set of words gives O(L) exact lookups but makes startsWith scan every stored word, O(N * L) per query, far too slow for 30000 operations on words up to 2000 characters. Storing every prefix of every word in a set works but can blow up memory.
Approach
- Each node holds a mapping from character to child and a flag indicating a word ends here. The root is an empty node.
- insert: walk from the root one character at a time, creating a child wherever the edge is missing. Set the flag on the final node.
- search: walk the same way, but return false as soon as an edge is missing. If the walk completes, return the final node's flag.
- startsWith: walk the same way and return true if the walk completes, regardless of the flag.
- Choose child storage deliberately: a 26-slot array gives constant-time indexing but costs 26 pointers per node; a hash map saves memory when branching is sparse, which matters when 30000 long insertions could create tens of millions of nodes.
Walkthrough of Example 1
Trie(); insert("car"); search("ca"); startsWith("ca"); search("car") → [null,null,false,true,true]
- insert(car): the root has no c child, so create it; then create a under c, then r under a; mark r as a word end.
- search(ca): walk c then a; both exist, but the a node's flag is false, so return false.
- startsWith(ca): walk c then a; the path exists, so return true.
- search(car): walk c, a, r; the r node's flag is true, so return true.
- Outputs: null, null, false, true, true.
Time and space
Time O(L) · Space O(T). L is the argument length; each operation walks at most L nodes. T is the total characters inserted, an upper bound on nodes; with fixed 26-slot child arrays multiply by the alphabet size.
Interview pitfalls
- Returning true from search when the path exists but the end flag is unset; the example is built to catch this.
- Inserting a word that is a prefix of an existing word (insert car, then ca) must set the flag on the existing a node, not create a new branch.
- Inserting the same word twice must be idempotent; do not allocate or double-mark.
- Off-by-one when converting characters to array indexes, especially forgetting to subtract the code of a.
Follow-up questions interviewers ask
- Add a delete operation that prunes nodes no longer on any word's path.
- Support wildcard characters in search, as in Design Add and Search Words.
- Return all words with a given prefix, or the most frequent k completions, as in autocomplete.
Further reading on the technique: Trie
Related LeetCode Problems
Practice more problems similar to Implement Trie (Prefix Tree).
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.