Implement Trie (Prefix Tree)

PracticeNeetCode ↗LeetCode ↗

Design a trie (prefix tree) that supports three operations: inserting a word, checking whether an exact word has been inserted, and checking whether any inserted word starts with a given prefix.

Example

Key Pointers

• Each node holds a map of children (one entry per next character) plus a boolean marking "a full word ends here."
• Insert and search share the same walk: follow children character by character, creating nodes as you go (insert) or bailing out the moment a child is missing (search).
• search and startsWith differ only in the final check — search requires the end-of-word flag, startsWith doesn't care.

Step-by-Step Analysis

1. Represent each node with a dict of children and a boolean is_end.
2. Insert: starting at the root, for each character create a child if it doesn't exist, then move into it; mark is_end = True at the last node.
3. Search: walk the same way; if any character's child is missing, return False. At the end, return the node's is_end flag.
4. startsWith: the identical walk as search, but return True as soon as the prefix is fully consumed, regardless of is_end.

Complexity

Time: O(L) per operation, where L is the word/prefix length — Space: O(N · L) across all inserted words in the worst case

Code

class TrieNode:
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.is_end = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_end

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True

Code Explanation

How the solution above works, piece by piece.

1. Each TrieNode has children (character → node) and is_end, which marks that a whole word stops here.
2. insert: walk from the root, creating a child for each character that doesn't exist yet, then set is_end on the last node.
3. search: follow the characters; a missing child means the word isn't there. At the end, return is_end, because a path alone might just be a prefix of a longer word ("app" in "apple").
4. startsWith: same walk, but any complete path counts, so return True.
5. All three are O(L) for a word of length L, independent of how many words are stored.

Visual Walkthrough

Running the example calls:

Video Explanation

NeetCode — LeetCode 208