Implement Trie (Prefix Tree)

Problem

Search engines and IDEs need to answer two different questions about text: does this exact string exist, and does any stored string start with this prefix? A hash set handles the first in O(m) but cannot answer the second without scanning everything. Implement a trie that answers both in O(m) per query.

Example 1:

Input: ["Trie", "insert", "search", "search", "starts_with", "insert", "search"]
[[], ["grape"], ["grape"], ["grap"], ["grap"], ["grap"], ["grap"]]
Output: [null, null, true, false, true, null, true]
Explanation: after inserting "grape", searching "grap" returns False because "grap" was only a prefix; after inserting "grap" explicitly, the search returns True.

Constraints:

1 <= word.length, prefix.length <= 1000
word and prefix consist only of lowercase English letters.
At most 10^4 calls in total will be made to insert, search, and starts_with.

Try it

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word: str) -> None:
        pass
    def search(self, word: str) -> bool:
        pass
    def starts_with(self, prefix: str) -> bool:
        pass

Tests

trie = Trie()
trie.insert("grape")
assert trie.search("grape")==True, "grape was inserted"
assert trie.search("grap")==False, "grap is only a prefix"
assert trie.starts_with("grap")==True, "grap is a valid prefix"
trie.insert("grap")
assert trie.search("grap")==True, "grap now inserted"
assert trie.starts_with("d")==False, "no word starts with d"
assert trie.search("grae")==False, "grae not inserted"

Hints (3)

Solution Breakdown

Approach: Trie traversal - one shared character-by-character walk drives all three operations.

Each TrieNode carries a children dict (character to child node) and an is_end flag. insert walks the word one character at a time starting from the root; wherever an edge is missing it creates a fresh node with node.children[char] = TrieNode(), then advances. After the last character it sets node.is_end = True so the path is marked as a real word, not just a prefix that happens to exist. search and starts_with run the identical loop but never create nodes - the moment a character has no matching child they return False, because that path was never inserted. The single behavioral difference lives in the return statement after the loop: search returns node.is_end (the word must actually terminate there), while starts_with returns True (any continuation counts). That is why search("grap") is False after only insert("grape") - the p node exists but its is_end is still False. Insert "grap" and that same node flips to is_end = True, so a node can be both a word end and have children.

Edge cases: An empty-string search returns root.is_end (the loop never runs), and starts_with("") returns True since every trie trivially contains the empty prefix. A prefix that shares no first character returns False on the first lookup.

Complexity: O(m) time per operation, O(m) space per inserted word - m is the word or prefix length; each call touches exactly one node per character.

Implement Trie (Prefix Tree)

Problem

Solution Breakdown

Discussion