Pattern 18: Tries (Prefix Trees)

0. The Template (Copy-Paste Skeleton)

One node class, three methods. insert and search are the same 6-line walk; only the final check differs.

// TEMPLATE — TRIE (prefix tree) over lowercase a–z
class Trie {
    private static class Node {
        Node[] children = new Node[26];   // array beats HashMap for a fixed small alphabet
        boolean isWord;                   // marks the END of a complete word
    }

    private final Node root = new Node();

    public void insert(String word) {
        Node cur = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (cur.children[i] == null) cur.children[i] = new Node();   // create on demand
            cur = cur.children[i];
        }
        cur.isWord = true;                // WITHOUT this, "app" would match inside "apple"
    }

    public boolean search(String word)      { Node n = walk(word); return n != null && n.isWord; }
    public boolean startsWith(String prefix) { return walk(prefix) != null; }   // node exists = enough

    private Node walk(String s) {
        Node cur = root;
        for (char c : s.toCharArray()) {
            cur = cur.children[c - 'a'];
            if (cur == null) return null;
        }
        return cur;
    }
}

// WILDCARD SEARCH ('.' matches any character) — LC 211: branch on '.', otherwise walk
private boolean dfs(String w, int i, Node node) {
    if (node == null) return false;
    if (i == w.length()) return node.isWord;

    char c = w.charAt(i);
    if (c != '.') return dfs(w, i + 1, node.children[c - 'a']);

    for (Node child : node.children)                    // '.' → try every branch
        if (dfs(w, i + 1, child)) return true;
    return false;
}

// TRIE + GRID DFS — Word Search II (LC 212): the trie prunes dead branches instantly
// Store the whole word on the terminal node (`node.word = w`) instead of a boolean,
// then null it out after collecting to avoid duplicate results.

The rule everyone forgets

isWord is not optional. Without it, search("app") returns true for a trie containing only "apple", because the path exists. The node marks “a word ends here”, which is different from “this path exists” — and that difference is exactly search vs startsWith.

Node[26] vs Map<Character, Node>

	Node[26]	HashMap<Character, Node>
Lookup	array index — fastest possible	hash + equals
Memory	26 refs per node even if 1 is used	only what’s present
Alphabet	fixed, small (a–z, 0–1)	Unicode, mixed case, arbitrary
Use when	LeetCode constraints say lowercase English	real-world text, sparse nodes

Why a trie instead of a HashSet

A HashSet<String> answers “is this exact word present?” in O(L) too. The trie wins when you need prefix semantics:

• autocomplete / “all words starting with X”
• shared prefixes save memory — 10,000 words sharing “inter” store it once
• early termination during a search — in Word Search II you abandon a grid path the moment the prefix leaves the trie, which is what makes it feasible at all
• lexicographic ordering falls out of walking children 0→25 in order

Complexity

Operation	Time	Note
insert / search / startsWith	O(L)	L = word length — independent of how many words are stored
Build over n words	O(n · L)
Space	O(total characters × alphabet)	worst case; shared prefixes reduce it a lot
Wildcard search with .	O(26^d · L)	d = number of dots

---

1. Pattern Identification & Logic

How to Identify (Interview Triggers)

• “Implement autocomplete / search suggestions / typeahead”
• “Find words by prefix” / “starts with”
• “Word search in a grid with a dictionary” (LC 212 — DFS + Trie combo)
• “Implement a dictionary” with insert, search, startsWith
• “Wildcard search” with . matching any char (LC 211)
• “Longest common prefix” among many strings
• “Replace words with shortest root”
• IP routing, DNA / bioinformatics motif search
• Spell-checker / search engine suggestions

If the input is a collection of strings and you need to query by prefix, a Trie usually beats sorting + binary search and beats hashing on prefix queries.

The Algorithm (Pseudocode)

TrieNode:
    children[26]  or  HashMap<Character, TrieNode>
    isEnd  (boolean — marks end of a word)
    // optional: word (for retrieval), frequency, topK suggestions

insert(word):
    node = root
    for c in word:
        if node.children[c] == null:
            node.children[c] = new TrieNode()
        node = node.children[c]
    node.isEnd = true

search(word):
    node = traverse(word)
    return node != null && node.isEnd

startsWith(prefix):
    return traverse(prefix) != null

traverse(s):
    node = root
    for c in s:
        if node.children[c] == null: return null
        node = node.children[c]
    return node

The ‘Trick’ to Know

• Array vs HashMap children: TrieNode[26] is 5–10× faster for lowercase a–z (cache-friendly, no boxing). Use HashMap<Character, TrieNode> only when the alphabet is large/unknown (Unicode, mixed case, digits + symbols).
• isEnd is non-optional. Without it, apple and app are indistinguishable — both end somewhere along the same path.
• For autocomplete top-K, store a small bounded min-heap or sorted list at each prefix node OR walk subtree at query time (DFS). Trade memory vs query latency.
• For wildcard search (.), branch into ALL children at that level — DFS with backtracking.

---

2. Java Implementation (Brute Force vs. Optimal)

Example Problem: Implement Trie — LC 208

Brute Force: HashSet — O(L) insert/search but no prefix in O(L)

class Trie {
    Set<String> words = new HashSet<>();
    public void insert(String word) { words.add(word); }
    public boolean search(String word) { return words.contains(word); }
    public boolean startsWith(String prefix) {
        // O(n * L) — scan every word
        for (String w : words) if (w.startsWith(prefix)) return true;
        return false;
    }
}

Search is O(L) but startsWith is O(N · L). For autocomplete this dies.

Optimal: Trie with array children — O(L) for ALL three ops

class Trie {
    static class Node {
        Node[] children = new Node[26];
        boolean isEnd = false;
    }
    private final Node root = new Node();

    public void insert(String word) {
        Node node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) node.children[idx] = new Node();
            node = node.children[idx];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        Node node = traverse(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return traverse(prefix) != null;
    }

    private Node traverse(String s) {
        Node node = root;
        for (char c : s.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return null;
            node = node.children[idx];
        }
        return node;
    }
}

Java Architecture Insights

• static class Node: nested class without enclosing-instance reference is leaner. Use static whenever the inner class doesn’t need outer this.
• Why new Node[26] is fine: each branch is sparse — most nodes have 2–4 children allocated. Memory cost is roughly O(total chars in dictionary) for arrays vs O(unique paths) for HashMap — usually array wins for ASCII alphabets.
• For Unicode/case-sensitive: switch to Map<Character,Node> to avoid 65k-sized arrays.
• Encapsulate Node — don’t expose internals; expose only insert/search/startsWith (and findByPrefix for autocomplete extensions).

Optional optimization for autocomplete (LC 642, 1268)

Store top-K words at every node so a prefix query returns suggestions in O(P + K) without subtree traversal:

static class Node {
    Node[] children = new Node[26];
    PriorityQueue<String> topK;     // min-heap, capped at K
    boolean isEnd;
}

On insert, walk and update each node’s heap. Memory cost is higher; query cost drops dramatically. Classic trade.

---

3. Mental Model & Visualization

ASCII Diagram (insert: app, apple, apply, bat)

              root
              / \
             a   b
             |   |
             p   a
             |   |
             p*  t*
            / \
           l   l
           |   |
           e*  y*

* = isEnd marker

search("app") → walks root → a → p → p, isEnd ✓ → true search("apl") → walks root → a → p → l, l not under second p → false startsWith("apl") → traverse only, no isEnd check — false startsWith("ap") → traverse to second p, non-null → true

Senior Mental Trigger

“Prefix queries, autocomplete, or ‘design a search system’ → Trie. O(L) per op, scales to millions of strings, beats HashSet on prefix work.”

---

4. Curated Problem Lists

Commonly Asked (Bread & Butter)

#	Problem	Difficulty
LC 208	Implement Trie (Prefix Tree)	Medium
LC 211	Design Add and Search Words Data Structure	Medium
LC 648	Replace Words	Medium
LC 720	Longest Word in Dictionary	Easy
LC 14	Longest Common Prefix	Easy

FAANG ‘Aha!’ Level (Hard / Unintuitive)

#	Problem	Difficulty	Note
LC 212	Word Search II	Hard	Amazon, Google — DFS in grid + Trie pruning
LC 1268	Search Suggestions System	Medium	Amazon ★★★ — autocomplete top-3 per prefix
LC 642	Design Search Autocomplete System	Hard	Premium — top-K with hot-string scoring
LC 421	Maximum XOR of Two Numbers in an Array	Medium	Bit-trie!
LC 472	Concatenated Words	Hard	Trie + DP
LC 745	Prefix and Suffix Search	Hard	Double trie or {suffix}#{prefix} trick
LC 588	Design In-Memory File System	Hard	Premium — Trie-like dir tree
LC 425	Word Squares	Hard	Premium — Trie + backtracking

Frequency at MAANG (2026)

Pattern usage	Amazon	Meta	Google	Apple	Netflix
Tries	★	★★	★★	★	–

Search Suggestions (LC 1268) is on the Amazon hot list — comes up often in phone screens.

---

5. Time & Space Complexity Table

Op	Time	Space (per op)	Notes
insert(w)	O(L)	O(L) worst (all new)	L = word length
search(w)	O(L)	O(1)	Just traversal
startsWith	O(P)	O(1)	P = prefix length
delete(w)	O(L)	O(1)	Mark isEnd=false; optionally prune subtree
Autocomplete	O(P+K) with stored top-K, or O(P + subtree) without	varies	Trade memory vs latency
Total mem	—	O(Σ Lᵢ × alphabet)	Big-alphabet → use HashMap children

For a typical English dictionary (n = 100k words, avg L = 8), trie size is ~800k nodes × 28 bytes ≈ 22 MB with array children, ~10 MB with HashMap children — well within bounds.

---

6. Common Variants & Extensions

Variant	Tweak	Sample problem
Wildcard .	DFS branch into all children at .	LC 211 Add and Search Words
Bit-trie	32 levels, children[2] for 0/1 bits	LC 421 Maximum XOR
Suffix-trie / Suffix-array	Insert all suffixes for substring queries	LC 1044 Longest Duplicate Substring (advanced)
Compressed trie (radix)	Merge single-child chains	Routing tables, less common in interviews
Trie + DFS pruning	Use trie to short-circuit grid search	LC 212 Word Search II — classic hard combo
Trie + DP	Trie used as a “valid word” oracle	LC 472 Concatenated Words
Top-K per node	Min-heap stored at each node	LC 1268, LC 642 autocomplete

---

7. Interview Red Flags & Gotchas

• ❌ Forgetting isEnd — passes most cases but fails search("app") after only inserting "apple"
• ❌ Allocating new TrieNode[26] per char (instead of per node) — common typo, memory leak
• ❌ Using String.toCharArray() inside a hot loop on huge inputs — fine for interviews, but mention charAt(i) alternative
• ❌ Reading the problem as “find all words” and trying to do it without DFS over the trie — you need a subtree walk for that
• ❌ Confusing prefix with suffix — for suffix queries, insert reversed strings OR build a suffix trie
• ❌ For LC 212 Word Search II: not pruning the trie as you find words is the #1 reason it TLEs. After matching a word, set its isEnd=false and prune leaf chains so the DFS shrinks.

---

8. Companion 90-second Pitch (verbal)

“When I see prefix queries, autocomplete, or dictionary-style word lookup, I reach for a Trie. Each node has up to 26 children for lowercase ASCII and an isEnd flag. Insert, search, and prefix-check are all O(L). For autocomplete I’d store a small top-K heap at each node so prefix queries return suggestions in O(P + K) without subtree traversal. The classic combo is Trie + DFS for grid-word problems — the trie prunes branches the moment a prefix can’t extend to any word.”

A perfect opener for LC 208/211/212/1268 and any “design a search box” question.