Implement Trie (Prefix Tree)
Design a trie with insert(word), search(word), and startsWith(prefix).
Intuition
A trie stores words character by character down a tree: each node has up to 26 children, and words sharing a prefix share a path. Insert walks the word, creating missing children; search walks and checks an end-of-word flag; startsWith is the same walk without the flag. Every operation costs the word's length — independent of how many words are stored.
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
Node = children map + flag
Each node: dict char→child, plus end marking that some word terminates here. The flag is what separates search('app') from startsWith('app') when only 'apple' was inserted.
Insert = walk and create
From the root, follow each character's child, creating nodes as needed; set end on the last.
Search vs prefix
Both walk the same way and fail on a missing child. search additionally requires node.end at the last character.
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.