patternDSA/Trie

Core Pattern → Pattern 26

Trie (Prefix Tree)

Strings that share prefixes share nodes. One traversal of m characters answers any prefix query in O(m) — regardless of how many words are in the dictionary. HashSet can't do that.

Frequency:★★★★☆

·~30 min·Intermediate·5 problems

Prev Depth-First Search (DFS)

The Core Shock

HashSet: exact match in O(m) but prefix query = O(n·m). Trie: prefix query in O(m) — n doesn't matter.

HashSet / linear scan

O(n·m) prefix

Check every word in the dictionary against the prefix. 10,000 words × 10 chars = 100,000 comparisons per query.

Trie prefix query

O(m) always

Walk m nodes. The entire dictionary is irrelevant — you just traverse the shared prefix path once.

The Trie's secret: shared prefixes share nodes. "cat", "car", "card", "care" all share the nodes c→a. Insert all four words and you create 6 nodes, not 14 characters.

TrieNode: children + is_end

Two fields. That's the entire data structure.

children

dict[str, TrieNode]

Maps each character to the next node. Up to 26 entries for lowercase English. Use {} (empty dict) not a 26-element array — sparser and simpler in Python.

if ch not in node.children:
    node.children[ch] = TrieNode()
node = node.children[ch]

is_end

bool (default False)

True when a complete word ends at this node. Multiple words can share a node — only the ones that end here have is_end=True. This distinguishes 'car' from 'card'.

# At end of insert:
node.is_end = True

# In search:
return node.is_end

search vs starts_with differ by one word:
search: return node.is_end — must be a complete word
starts_with: return True — any continuation counts

The 3-Step Framework

Insert all, then query any prefix in O(m).

Build the Trie — insert all words

For each word, walk from root character by character. If a node for the character doesn't exist, create it. After processing the last character, set is_end=True. Time: O(total characters inserted).

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

Always start from self.root, never from a stored node — each insert is independent. The root itself holds no character; it's the entry point for all words.

Navigate to the prefix node

For any query (search, starts_with, suggestions, index pairs): walk from root following the query characters. If any character is missing, the prefix/word doesn't exist — return False/None immediately.

node = self.root
for ch in prefix:
    if ch not in node.children:
        return None   # prefix absent
    node = node.children[ch]
return node   # the prefix node

Factor this out as get_prefix_node() — every Trie problem uses it. Search: walk + check is_end. Starts_with: walk + return True. Suggestions: walk + DFS collect.

DFS collect words from prefix node

For autocomplete/suggestions: DFS from the prefix node. Accumulate the path suffix. When is_end=True, add current_prefix+suffix to results. Iterate sorted(node.children) for lexicographic order.

def collect(node, prefix, results, limit=3):
    if len(results) >= limit: return
    if node.is_end:
        results.append(prefix)
    for ch in sorted(node.children):
        collect(node.children[ch],
                prefix+ch, results, limit)

sorted(node.children) gives lexicographic order — essential for 'top 3 suggestions' problems. The early return (len(results) >= limit) prunes the DFS once enough results are found.

Pattern Recognition

'prefix', 'autocomplete', 'dictionary lookup', 'wildcard' → Trie.

Use Trie When

"Implement autocomplete / search suggestions"

Multiple prefix queries against same dictionary

Wildcard pattern matching ("." matches any char)

"Find all words starting with prefix X"

Index pairs: find all dictionary words in text

Word search in grid (Trie prunes invalid prefixes)

"Extra characters": split string using dictionary

Any problem needing O(m) prefix lookup

Common Pitfalls

search returns True on prefix — should check node.is_end

starts_with checks is_end — should just return True

Forgetting to start from root on every operation (not cached node)

Wildcard '.': only try children.values() — not checking char against '.'

collect_words: not sorting children → non-lexicographic suggestions

Sharing TrieNode instances — mutations affect all words sharing that node

Not handling empty string insert (is_end on root = True)

Trie + DP: advancing i in the inner loop, not the outer dp loop

On this page