Implement Trie (Prefix Tree)

• Difficulty: Medium
• Topics: Hash Table, String, Design, Trie
• Link: https://leetcode.com/problems/implement-trie-prefix-tree/

Problem Description

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

• Trie() Initializes the trie object.
• void insert(String word) Inserts the string word into the trie.
• boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
• boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

Constraints:

• 1 <= word.length, prefix.length <= 2000
• word and prefix consist only of lowercase English letters.
• At most 3 * 104 calls in total will be made to insert, search, and startsWith.

Solution

1. Problem Deconstruction

Technical Rewrite

A trie is a rooted tree structure for storing dynamic string sets with the following formal specifications:

• Node Definition: Each vertex $v$ contains:
  • A mapping $δ(v, c): \Sigma \rightarrow V$ (child nodes, $\Sigma = \{a..z\}$)
  • A terminal flag $\text{isEnd}(v) \in \{0,1\}$
• Operations:
  1. Insert($w$):
     $v_0 \leftarrow \text{root}$
     $\text{for } i=1 \text{ to } |w|$:
     $\quad v_i = \begin{cases} \delta(v_{i-1}, w_i) & \text{if exists} \\ \text{newNode}() & \text{else} \end{cases}$
     $\text{isEnd}(v_{|w|}) \leftarrow 1$
  2. Search($w$):
     $v \leftarrow \text{root}$
     $\text{for } i=1 \text{ to } |w|$:
     $\quad \text{if } \delta(v, w_i) \text{ undefined: return } \bot$
     $\quad v \leftarrow \delta(v, w_i)$
     $\text{return } \text{isEnd}(v)$
  3. startsWith($p$):
     $v \leftarrow \text{root}$
     $\text{for } i=1 \text{ to } |p|$:
     $\quad \text{if } \delta(v, p_i) \text{ undefined: return } \bot$
     $\quad v \leftarrow \delta(v, p_i)$
     $\text{return } \top$

Beginner Rewrite

Imagine organizing words in a tree where each branch represents a letter. To store “apple”:

• Start at root → ‘a’ → ‘p’ → ‘p’ → ‘l’ → ‘e’ (mark ‘e’ as word end).
  Operations:
• Insert: Build letter-by-letter branches.
• Search: Follow letters to check if path exists AND last letter is marked as word end.
• startsWith: Follow letters to check if path exists (last letter doesn’t need to be word end).

Mathematical Rewrite

Let $\mathcal{W}$ be the set of inserted words. Define trie $T = (V, E, \rho)$ where:

• $\rho$: root node
• $V \ni v$ has $\text{isEnd}: V \rightarrow \mathbb{B}$
• $E \subseteq V \times \Sigma \times V$ (labeled edges)
  Invariant: $\forall w \in \mathcal{W}$, $\exists!$ path $\rho \xrightarrow{w_1} v_1 \xrightarrow{w_2} \cdots \xrightarrow{w_k} v_k$ with $\text{isEnd}(v_k)=1$.
  Operations maintain this invariant via edge additions and $\text{isEnd}$ updates.

Constraint Analysis

1. $1 \leq |\text{word}|, |\text{prefix}| \leq 2000$:
   • Limits worst-case per-op steps to 2000 → $O(2000)$ per op acceptable.
   • Edge Case: Max-length words amplify memory consumption (node explosion).
2. Lowercase letters only ($\|\Sigma\|=26$):
   • Permits fixed-size child arrays (26 pointers/node).
   • Edge Case: Alphabet constraint simplifies child storage but wastes space for sparse nodes.
3. Total calls $\leq 3 \times 10^4$:
   • Worst-case: $3 \times 10^4$ inserts → $3 \times 10^4 \times 2000 = 6 \times 10^7$ nodes.
   • Edge Case: Memory explosion (12+ GB in Python) if no shared prefixes.

---

2. Intuition Scaffolding

Analogies

1. Real-World (Postal System):
   • Root = main post office.
   • Child nodes = regional hubs (routed by zip code digits).
   • $\text{isEnd}$ = delivery destination exists.
   • Why relevant: Hierarchical prefix matching mirrors zip code lookup.
2. Gaming (RPG Skill Tree):
   • Nodes = combat moves.
   • Path = combo sequence.
   • Search = exact combo exists.
   • startsWith = partial combo valid.
3. Math (Finite Automaton):
   • Trie = DFA with states $V$, alphabet $\Sigma$.
   • $\text{isEnd}$ = accepting states.
   • Search = $w$ lands in accepting state.
   • startsWith = $p$ is a valid path.

Common Pitfalls

1. Missing Terminal Flags:
   • Insert(“apple”) → Search(“app”) returns $\top$ incorrectly.
2. Shared-Prefix Overwrite:
   • Insert(“app”) after “apple” fails to mark ‘p’ as terminal.
3. Case Sensitivity:
   • Assuming uppercase support when problem specifies lowercase.
4. Linear Child Search:
   • Using lists instead of dicts/arrays → $O(26)$ per char vs $O(1)$.
5. Memory Bloat:
   • Fixed-size arrays (26 children/node) waste $>200$ bytes/node.
   • Solution: Dictionary for sparse children.

---

3. Approach Encyclopedia

Brute Force (List Storage)

class BadTrie:
    def __init__(self):
        self.words = set()  # Stores all inserted words
        
    def insert(self, word):
        self.words.add(word)  # O(1) amortized
        
    def search(self, word):
        return word in self.words  # O(n) per op
        
    def startsWith(self, prefix):
        for w in self.words:  # O(n*L)
            if w.startswith(prefix):
                return True
        return False

Complexity:

• Time: Insert $O(1)$, Search $O(n)$, StartsWith $O(n \times L)$
• Space: $O(n \times L)$ (store all words)
  Why Fail:
• $n \leq 3 \times 10^4$, $L \leq 2000$ → StartsWith worst-case $6 \times 10^7$ per call → $>10^{12}$ ops total.

Optimal (Trie with Dict Children)

Visualization (Insert “apple”, “app”):

root: {}  
  insert("apple"):  
    root → 'a' → Node1 (children={})  
    Node1 → 'p' → Node2  
    Node2 → 'p' → Node3  
    Node3 → 'l' → Node4  
    Node4 → 'e' → Node5 (isEnd=True)  
  insert("app"):  
    root → 'a' → Node1 → 'p' → Node2 → 'p' → Node3  
    set Node3.isEnd = True  

Pseudocode:

class TrieNode:
  children: dict  # char → TrieNode
  is_end: bool

class Trie:
  __init__():
    root = TrieNode()
  
  insert(word):
    node = root
    for c in word:
      if c not in node.children:
        node.children[c] = TrieNode()
      node = node.children[c]
    node.is_end = True
  
  search(word):
    node = root
    for c in word:
      if c not in node.children: 
        return False
      node = node.children[c]
    return node.is_end
  
  startsWith(prefix):
    node = root
    for c in prefix:
      if c not in node.children: 
        return False
      node = node.children[c]
    return True  # Path exists

Complexity Proof:

• Time: $O(L)$ per op (each char processed once).
• Space: $O(T)$ where $T = \text{number of nodes}$.
  • Worst-case: $O(\sum_{\text{words}} |w|)$ (no shared prefixes).
  • Best-case: $O(|\text{longest word}|)$ (all words share prefix).

---

4. Code Deep Dive

class TrieNode:
    def __init__(self):
        self.children = {}  # Dict avoids fixed-size array waste
        self.is_end = False  # Marks word termination

class Trie:
    def __init__(self):
        self.root = TrieNode()  # Dummy root (no char)
    
    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            # If child missing, create new node
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]  # Move down
        node.is_end = True  # Mark final node as word end
    
    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False  # Prefix broken
            node = node.children[char]
        return node.is_end  # Must be exact word end
    
    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False  # Prefix broken
            node = node.children[char]
        return True  # Path exists (regardless of is_end)

Edge Case Handling:

1. Duplicate Insertions (e.g., insert “app” twice):
   • insert retraverses path, sets is_end=True (idempotent).
2. Substring Search (e.g., “app” after “apple”):
   • Initial search("app") fails (is_end=False at second ‘p’).
   • After inserting “app”, is_end set → returns true.
3. Max-Length Words:
   • Loop runs 2000 times → no stack overflow (iterative).

---

5. Complexity War Room

Hardware-Aware Analysis:

• Time: $3 \times 10^4$ ops × $2000$ chars = $6 \times 10^7$ steps → ~0.6 sec (Python).
• Space:
  • Worst-case: $6 \times 10^7$ nodes.
  • Per node: Dict overhead ~240B + 1B bool → 241B/node.
  • Total: $6 \times 10^7 \times 241 \text{B} = 14.46$ GB (critical in constrained env).
• Optimization: Use __slots__ or C++ for production.

Industry Comparison Table:

Approach	Time	Space	Readability	Interview Viability
Brute Force (List)	$O(n \cdot L)$	$O(n \cdot L)$	★★★★★	❌ (Fails large $n$)
Trie (Array)	$O(L)$	$O(26 \cdot T)$	★★★☆☆	✅ (Alphabet known)
Trie (Dict)	$O(L)$	$O(T)$	★★★★☆	✅ (Optimal)

---

6. Pro Mode Extras

Variants:

1. Wildcard Search (LC 211):
   • Modify search to handle ‘.’ via DFS/BFS on all children.

   def search(self, word: str) -> bool:
        def dfs(node, i):
            if i == len(word): 
                return node.is_end
            if word[i] == '.':
                for child in node.children.values():
                    if dfs(child, i+1): 
                        return True
                return False
            else:
                if word[i] not in node.children: 
                    return False
                return dfs(node.children[word[i]], i+1)
        return dfs(self.root, 0)
   

2. Compressed Trie:
   • Merge chain of single-child nodes → store substrings.
   • Cuts $O(T)$ to $O(\text{\# distinct prefixes})$.

Interview Cheat Sheet:

• First Mention: “Trie ops are $O(L)$ time, $O(L)$ space per insertion.”
• Edge Cases: “Handle empty strings? Constraints say $L \geq 1$.”
• Optimization Path:
  1. Dict children for memory.
  2. __slots__ to reduce Python overhead.
  3. C++ for pointer control.