Skip to content
DSA Grind
All 26 sections

Blind 75 — Trie (Prefix Tree) Pattern Guide

Pattern guideUpdated
On this page

How to Identify a “Trie” Problem

Interview Triggers

  • “Dictionary of words” — repeated prefix queries
  • “Autocomplete” / “starts with”
  • “Add and search word” — wildcards in search
  • Word-search on a 2-D board with many target words (LC 212)
  • Longest common prefix among N strings (when frequent queries)
  • “Replace words with shortest root”

Which Sub-Pattern Does It Belong To?

If the prompt says… Use this sub-pattern Example LC
Implement insert/search/startsWith Trie with children[26] 208
Search with . wildcards Trie + DFS branching on . 211
Find all dictionary words on a 2-D board Trie + grid DFS 212

The Decision Tree

TRIE PROBLEM
│
├─ Prefix queries on a dictionary?
│   └─ Build Trie once, answer in O(L) per query → LC 208
│
├─ Wildcard / pattern match in dictionary?
│   └─ Trie + DFS — branch on `.`  → LC 211
│
└─ Many target words to find in text/grid?
    └─ Trie + DFS, prune dead branches → LC 212

Reusable Templates

Bare-bones TrieNode

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd;
}

Insert / Search / StartsWith (LC 208)

class Trie {
    TrieNode root = new TrieNode();
    public void insert(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (cur.children[i] == null) cur.children[i] = new TrieNode();
            cur = cur.children[i];
        }
        cur.isEnd = true;
    }
    public boolean search(String word) { TrieNode n = walk(word); return n != null && n.isEnd; }
    public boolean startsWith(String pre) { return walk(pre) != null; }
    private TrieNode walk(String s) {
        TrieNode cur = root;
        for (char c : s.toCharArray()) { if ((cur = cur.children[c - 'a']) == null) return null; }
        return cur;
    }
}

Search with . Wildcard (LC 211)

boolean dfs(String word, int idx, TrieNode node) {
    if (node == null) return false;
    if (idx == word.length()) return node.isEnd;
    char c = word.charAt(idx);
    if (c == '.') {
        for (TrieNode child : node.children)
            if (dfs(word, idx + 1, child)) return true;
        return false;
    }
    return dfs(word, idx + 1, node.children[c - 'a']);
}

Trie + Grid DFS (LC 212)

1. Build a trie of all target words.
2. For every cell of the grid, run DFS:
   - Follow trie pointer for current letter; if null, prune.
   - If `isEnd` is hit, collect word (and set isEnd=false to dedupe).
3. Backtrack: mark cell with '#', recurse 4 directions, restore.

Bread & Butter Problems

# Problem LC # Difficulty Sub-Pattern
1 Implement Trie (Prefix Tree) 208 Medium TrieNode[26]

FAANG “Aha!” Problems

# Problem LC # Difficulty Sub-Pattern
1 Add and Search Word 211 Medium Trie + DFS wildcard
2 Word Search II 212 Hard Trie + grid DFS

Java Implementation Tips

  • For 26 lowercase letters, TrieNode[26] is faster than HashMap<Character, TrieNode>.
  • For Unicode / mixed-case, use HashMap<Character, TrieNode>.
  • “Word found” optimization in LC 212: after collecting a word, set isEnd = false so you don’t return duplicates.
  • Pruning: if a node has no children and isEnd == false, you can remove it from its parent (useful in LC 212 to speed up DFS).
  • Memory: each TrieNode with [26] array is ~100B+ — if you have 10^5 short words, memory adds up. Switch to HashMap if memory-bound.

Senior Mental Trigger

“Many prefix queries on a dictionary → Trie. Wildcards → Trie + DFS. Many target words in text/grid → Trie + DFS with pruning.”