Domain 2MediumCORE

Implement Trie (Prefix Tree)

We need to implement a data structure called a Trie (Prefix Tree) that supports three operations efficiently: insert, search, and startsWith. - Inputs: Strings (word or prefix) 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: search requires the full path and an end-of-word marker, whereas startsWith only checks if a valid prefix path exists regardless of whether it ends there or continues further down the tree.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Design#Trie

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 (word or prefix) 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: search requires the full path and an end-of-word marker, whereas startsWith only 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 O(N⋅L)O(N \cdot L) time complexity per operation, where NN is the number of stored strings and LL 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

  1. Node Structure: Define a helper class TrieNode with 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.
  2. Initialization: Create a root node (empty children, no is_end).
  3. 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, set is_end = True on the final node.
  4. 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 where is_end == True, return True.
  5. 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: O(L)O(L) per operation (where LL 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 (3⋅1043 \cdot 10^4 calls ×\times avg length).
  • Space Complexity: O(N⋅L)O(N \cdot L) 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 insert is called with a word already in the Trie, the loop simply traverses existing nodes and sets is_end_of_word = True again. This has no negative side effects; it remains idempotent.
  • Prefix vs Word Search: The logic explicitly checks node.is_end_of_word for search. 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 ≥1\ge 1, 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).