Implement Trie (Prefix Tree)
Implement Trie (Prefix Tree): design a trie with insert(word), search(word), and startsWith(prefix).
- 1 <= word.length, prefix.length <= 2000
- word and prefix consist only of lowercase English letters.
- At most 3 * 10⁴ calls in total will be made to insert, search, and startsWith.
Intuition
To implement trie prefix tree you build a structure supporting insert, search and startsWith. A hash set of words handles the first two, but fails at the third: asking whether any stored word begins with a prefix would mean scanning every word.
A trie fixes that by storing words character by character down a tree. Each node represents a prefix, and its children are the characters that can follow. Words sharing a prefix share the path that spells it — "apple" and "app" traverse the same three nodes before diverging.
That structure makes a prefix query trivial: walk the prefix's characters from the root, and if you never fall off, some word starts with it.
The one piece of state that is easy to underestimate is the end-of-word flag:
- A node needs a boolean marking that some word terminates exactly here.
Without it, search("app") and startsWith("app") are indistinguishable — after inserting only "apple", the path for "app" exists, so a flagless trie would wrongly report "app" as a stored word. The flag is the entire difference between the two operations, which otherwise share identical traversal code.
The cost is the property worth noticing: every operation is O(L) in the word's length and completely independent of how many words the trie holds. A million stored words do not slow down a five-character lookup.
A trie is the right structure when queries are about prefixes rather than whole keys. A hash set answers "is this exact word present?" in O(1) but can say nothing about startsWith without scanning every key. The trie's shape is the answer: shared prefixes share a path, so reaching a node means that prefix exists. Reach for it for autocomplete, word-search-II, and any problem where many strings share leading characters.
Approach
Before reading on: price up what counting everything costs here, then ask what the shared prefixes let you avoid storing twice. Aim for O(L) per op time and O(total chars) space.
Give each node children plus a flag
A node holds a map from character to child node, and a boolean isEnd. The flag is what separates a stored word from a mere prefix, and omitting it is the single most common bug in this problem.
Insert by walking and creating
From the root, follow the child for each character, creating a node when one is missing. After the final character, set isEnd = true on that node — marking the word's termination, not merely its path.
Search by walking and checking the flag
Follow the characters from the root. If any child is missing, return false. At the end, return node.isEnd — the path existing is not enough, since it may belong to a longer word.
Implement startsWith as the same walk
Identical traversal, but return true as soon as the walk completes regardless of isEnd. This is the operation a hash set cannot answer without scanning every stored word, and the reason the trie exists.
Choose the children representation
A fixed array of 26 slots gives O(1) indexing with predictable memory; a hash map handles arbitrary alphabets and stays small on sparse tries. Pick based on the alphabet size, and say why when asked.
Cost of the operations
All three operations are O(L) in the length of the word or prefix, independent of the number of stored words. Space is O(total characters) in the worst case, but shared prefixes mean real dictionaries use far less.
Solution & live demo
Common pitfalls
Not marking word ends
def insert(self, word):
node = self.root
for ch in word:
node = node.setdefault(ch, {}) ...
node["$"] = TrueAfter inserting "apple", searching "app" would succeed — the path exists as an interior stretch of a longer word. Without an explicit terminal flag a trie cannot distinguish a stored word from a mere prefix, which is the entire difference between search and startsWith.
Making search and startsWith identical
def search(self, word):
return self._walk(word) is not Nonedef search(self, word):
node = self._walk(word)
return node is not None and "$" in nodestartsWith only needs the path to exist; search also needs the end-of-word flag at the final node. Sharing the walk is good, but the terminal check is what separates them.
Using a character that can appear in the input as the flag
node["end"] = True
node["$"] = True
The flag shares the dictionary with child links, so it has to be a key no real character can collide with. "end" is safe only because it's multi-character — a single letter like "e" would be indistinguishable from a child edge and would corrupt the tree.
Edge cases
Walk succeeds but end is False → False.
No new nodes; just flag an interior node as end.
Idempotent — walk exists, flag already set.