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.

trie.insert("apple")
trie.search("apple")      → True
trie.search("app")        → False   (prefix only, not inserted)
trie.starts_with("app")   → True
trie.insert("app")
trie.search("app")        → True

Solution

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("app") is False after only insert("apple") - the second p node exists but its is_end is still False. Insert "app" 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.