LeetCode 208: Implement Trie (Prefix Tree) — Python Solution

LeetCode 208: Implement Trie (Prefix Tree) is a Medium trie problem. This Python walkthrough develops a nested child maps solution, ties every code decision to a concrete invariant, and includes the regression check used before publication.

This independent guide paraphrases the task rather than reproducing LeetCode’s prompt. Use the official page for the exact statement, examples, constraints, and submission runner.

Recognizing the pattern

A trie shares storage and work across common prefixes, allowing a search to abandon an entire family of words after one failed edge.

For this problem specifically, each character follows or creates a child node, and a terminal flag distinguishes complete words from prefixes. The invariant worth writing beside the code is: The node reached after a prefix represents exactly that character sequence.

Step-by-step algorithm

1. Identify the input state consumed by insert(word) and initialize the data required by the nested child maps pattern.
2. Each character follows or creates a child node, and a terminal flag distinguishes complete words from prefixes.
3. After each update, verify the page’s central invariant: The node reached after a prefix represents exactly that character sequence.
4. Finish only after the boundary behavior is covered: An inserted word can also be a prefix of a longer word.

Python solution

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word):
        node = self.root
        for char in word: node = node.setdefault(char, {})
        node["$"] = True

    def search(self, word):
        node = self._find(word)
        return node is not None and "$" in node

    def startsWith(self, prefix):
        return self._find(prefix) is not None

    def _find(self, text):
        node = self.root
        for char in text:
            if char not in node: return None
            node = node[char]
        return node

Reading the implementation

The main entry point is insert(word). The named working state includes node; those variables make the nested child maps state visible instead of hiding it in incidental control flow.

The implementation uses 2 loops with separate responsibilities, so preprocessing and the main traversal can each stay linear in their own input. Early returns stop as soon as the answer is forced, avoiding work that cannot change the result. In concrete terms, each character follows or creates a child node, and a terminal flag distinguishes complete words from prefixes.

Correctness argument

Initialization. The data structure starts with exactly the information known before any input element is processed.

Preservation. Each character follows or creates a child node, and a terminal flag distinguishes complete words from prefixes. Each update records the current item without invalidating earlier decisions; consequently, the node reached after a prefix represents exactly that character sequence.

Termination. The traversal consumes a finite input or finite state space. At the end, the invariant covers the complete input, which is precisely the condition required for the returned result.

Complexity and trade-offs

O(L) time per operation and O(total inserted characters) space. The auxiliary-space figure excludes the returned output unless the output itself is the structure being built.

A hash set is simpler for exact words, but it cannot answer prefix or wildcard traversal without examining many candidates. That comparison is useful in an interview because it explains why the final implementation is preferable, not merely that it passes.

Regression check

The published implementation belongs to a 100-problem suite that is compiled and exercised behaviorally before deployment.

One reference assertion from that suite is shown below. It targets the normal path while the edge conditions in the next section cover the failure-prone boundaries.

trie=Trie(); trie.insert("apple"); assert trie.search("apple") and trie.startsWith("app") and not trie.search("app")

Common mistakes and edge cases

• Problem-specific boundary: An inserted word can also be a prefix of a longer word.
• Pattern-level pitfall: A prefix node is not necessarily a complete word; terminal markers and wildcard branching need separate handling.
• Invariant check: after every update, confirm that the node reached after a prefix represents exactly that character sequence.

Interview review checklist

• Explain why nested child maps matches the structure of this input.
• State the invariant in one sentence before tracing code: The node reached after a prefix represents exactly that character sequence.
• Derive O(L) time per operation and O(total inserted characters) space from how many times each element or state is visited.
• Test the boundary explicitly: An inserted word can also be a prefix of a longer word.

Browse the searchable 100 LeetCode Python Solutions hub. Previous: 127. Word Ladder · Next: 211. Design Add and Search Words Data Structure