Implement Trie
Build the prefix tree from scratch — three operations sharing one walk, and the flag that separates a word from a prefix
Problem Statement
Implement a trie supporting three operations:
| Operation | Returns |
|---|---|
insert(word) | nothing |
search(word) | true if the exact word was inserted |
startsWith(prefix) | true if any inserted word begins with it |
insert("apple")
search("apple") → true
search("app") → false inserted as a prefix only
startsWith("app") → true
insert("app")
search("app") → true now it is a word in its own rightIntuition
The example is the whole problem. After insert("apple"), the string "app" exists as a path but was never inserted as a word. search("app") must be false while startsWith("app") must be true.
A hash map cannot do this. It knows "apple" is present and nothing about prefixes without scanning every key.
The insight
Store one character per edge, and give every node a boolean: does a word end here?
All three operations are the same walk from the root, one character at a time. They differ only in what happens on failure and what is checked at the end:
| Operation | Missing child | On arrival |
|---|---|---|
insert | Create it | Set the flag |
search | Return false | Return the flag |
startsWith | Return false | Return true |
Write the walk once as a helper and the three methods become two lines each.
Approach
A node holds children and a flag
children maps a character to the next node. is_word marks a complete word ending here.
The root is an empty node
It represents the empty string and carries no character.
Walk, creating as you go — that is insert
For each character, create the child if absent, then descend. Set the flag at the end.
Walk, failing on absence — that is search and startsWith
Identical traversal. search returns the flag; startsWith returns true simply for having arrived.
Solution
class TrieNode:
def __init__(self) -> None:
self.children: dict[str, "TrieNode"] = {}
self.is_word = False
class Trie:
def __init__(self) -> None:
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_word = True
def search(self, word: str) -> bool:
node = self._walk(word)
return node is not None and node.is_word
def starts_with(self, prefix: str) -> bool:
return self._walk(prefix) is not None
def _walk(self, text: str) -> TrieNode | None:
"""Follow text from the root. None if the path breaks."""
node = self.root
for char in text:
if char not in node.children:
return None
node = node.children[char]
return nodesearch and starts_with share _walk entirely. The only difference is the extra is_word check — which is exactly the distinction the problem is testing.
Complexity Analysis
Time Complexity
O(L) per operation
Space Complexity
O(total characters)
Time — L is the length of the word or prefix. Every operation walks it once. Crucially this does not depend on how many words the trie holds: a five-letter lookup takes five steps whether the trie stores ten words or ten million.
Space — one node per distinct character position across all words. Shared prefixes are stored once, so a dictionary of related words is much cheaper than storing each string.
Edge Cases
Related Problems
- Replace Words — applying a trie to shortest-prefix matching
- Tries — why prefixes are the only reason to prefer this over a hash map
- Search Autocomplete — the same structure at scale