208. Implement Trie (Prefix Tree)
Model: qwen3.5:9b
Topics: Design,Trie
FAANG asked: 1
Acceptance rate: 52.5%
Problem Breakdown
We need to implement a data structure called a Trie (Prefix Tree) that supports three operations efficiently: insert, search, and startsWith.
- Inputs: Strings (
wordorprefix) consisting of lowercase English letters. Lengths are between 1 and 2000. - Outputs: Boolean results for search/starts-with, void (null) for insert.
- Implicit Constraints: We need to handle duplicate inserts gracefully (the word already exists). The distinction is crucial:
searchrequires the full path and an end-of-word marker, whereasstartsWithonly checks if a valid prefix path exists regardless of whether it ends there or continues further down the tree.
Intuition
A naive approach would be to store all words in a list and iterate through them for every query. This results in time complexity per operation, where is the number of stored strings and is string length. Given up to 30,000 calls, this will likely Time Limit Exceed (TLE).
The key insight is that many words share common prefixes (“apple”, “app”). We can store these characters in a tree structure where each node represents one character of the alphabet.
- If we encounter a child for a specific letter during traversal, it exists; otherwise, create it or return false.
- To distinguish between a prefix and a complete word, we need an explicit flag (e.g.,
is_end_of_word) on nodes that mark where a valid string terminates.
Approach
- Node Structure: Define a helper class
TrieNodewith two attributes:- A dictionary (
children) mapping characters to child nodes. - A boolean flag (
is_end) indicating if this node marks the end of an inserted word.
- A dictionary (
- Initialization: Create a root node (empty children, no is_end).
- Insert: Iterate through each character in
word. If a child for that char doesn’t exist on current node, create it. Move to that child. After the loop finishes, setis_end = Trueon the final node. - Search: Traverse from root using characters of
word. If any step fails (child missing), return False immediately. Only if we traverse all chars and reach a node whereis_end == True, return True. - StartsWith: Similar traversal to Search, but stop after processing the prefix length. Return True only if every character in the prefix exists as a path from root; do not check
is_end.
Complexity Analysis
- Time Complexity: per operation (where is string length). We traverse at most one node per character. Total time for all operations depends on total characters processed, which fits within limits ( calls avg length).
- Space Complexity: in the worst case (all words distinct and no shared prefixes), where we store one node per character. In practice with many shared prefixes, space is significantly lower than a list of strings or hash map approach for prefix queries.
Solution
class Trie:
class Node:
def __init__(self):
self.children = {} # Maps char -> Node instance
self.is_end_of_word = False
def __init__(self):
self.root = self.Node()
def insert(self, word: str) -> None:
node = self.root
for char in word:
if char not in node.children:
node.children[char] = self.Node()
node = node.children[char]
node.is_end_of_word = True
def search(self, word: str) -> bool:
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
# Must be a complete word marked as end of insertion
return node.is_end_of_word
def startsWith(self, prefix: str) -> bool:
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
# If path exists up to this point, it is a valid prefix
return True
Edge Cases Handled
- Duplicate Insert: If
insertis called with a word already in the Trie, the loop simply traverses existing nodes and setsis_end_of_word = Trueagain. This has no negative side effects; it remains idempotent. - Prefix vs Word Search: The logic explicitly checks
node.is_end_of_wordforsearch. If we insert “apple” but search “app”, the traversal succeeds, but returns False because that specific node isn’t marked as an end of word (unless “app” was also inserted). This correctly distinguishes between a prefix and a complete key. - Empty Prefix: Constraints state length , so we don’t need to handle empty strings explicitly in the logic flow, but
startsWith("")would naturally return True since it starts at root without traversing any children (loop doesn’t run).