11 — Tries (Prefix Trees)

What a trie is

A trie (pronounced "try", from retrieval) stores a set of strings as a tree where each edge is a character and each path from the root spells out a prefix.

Inserting ["cat", "car", "dog"] gives:

        (root)
        /    \
       c      d
       |      |
       a      o
      / \     |
     t   r    g
    (*) (*)  (*)          (*) = a word ends here

Notice "cat" and "car" share the path c → a. The shared prefix is stored once. That's the structural saving, but it isn't the main reason to use a trie.

The real reason: lookup cost doesn't depend on dictionary size

To check whether "car" is present, you walk 3 edges. It takes 3 steps whether the trie holds 10 words or 10 million. Cost is O(L) in the word length, independent of n.

A HashSet also does exact lookup in O(L) (hashing reads the whole string). So for plain exact-match, a trie gives you nothing — use a HashSet.

What a trie can do that a hash set cannot

The last row is where tries earn their keep. Knowing that no word continues down this path lets you abandon a search immediately. That negative answer is what makes Word Search II tractable.

Node design

Two options; pick by alphabet size.

// Fixed lowercase alphabet — faster, O(1) child access by index
class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isWord = false;
}

// Arbitrary characters — smaller when the tree is sparse
class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isWord = false;
}

The trade: the array form allocates 26 references per node even for a single-child chain. Storing n words of length L costs up to O(26 · n · L) references. The map form allocates only what's used but pays hashing on every step. Mention the trade rather than pretending the array is free.

Why isWord must be a separate flag

A node existing does not mean a word ends there.

After inserting "apple", the node at path a-p-p exists — it's on the way to "apple". But "app" is not in your set. Without the flag you'd wrongly report it as present.

This is the classic trie bug. The flag distinguishes "this path is a prefix of something" from "this path is itself a word".

Implement Trie

class Trie {
    private final 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();  // create on demand
            cur = cur.children[i];
        }
        cur.isWord = true;              // mark the END of a word
    }

    public boolean search(String word) {
        TrieNode node = find(word);
        return node != null && node.isWord;      // BOTH conditions
    }

    public boolean startsWith(String prefix) {
        return find(prefix) != null;             // existence alone suffices
    }

    private TrieNode find(String s) {
        TrieNode cur = root;
        for (char c : s.toCharArray()) {
            cur = cur.children[c - 'a'];
            if (cur == null) return null;        // path doesn't exist
        }
        return cur;
    }
}

The only difference between search and startsWith is the isWord check. Factoring out find makes that visible — and reads far better than duplicating the walk. Say this when you write it.

Trace after inserting "apple":

Wildcard search (Design Add and Search Words)

A . matches any single character. The walk becomes a DFS that branches at every dot.

public boolean search(String word) {
    return dfs(word, 0, root);
}

private boolean dfs(String word, int i, TrieNode node) {
    if (node == null) return false;              // walked off the trie
    if (i == word.length()) return node.isWord;  // consumed the word — is it a real word?

    char c = word.charAt(i);
    if (c == '.') {
        for (TrieNode child : node.children) {
            if (child != null && dfs(word, i + 1, child)) return true;   // any match wins
        }
        return false;                            // no child matched
    }
    return dfs(word, i + 1, node.children[c - 'a']);
}

Why the body needs no null checks: passing node.children[c - 'a'] — possibly null — straight into the recursive call is safe, because line 1 handles it. Pushing the null check into the base case keeps the rest clean.

Complexity: O(L) with no dots, O(26^d · L) with d dots. The exponent is in the number of dots, not the word length — say it that way.

Leading dots are the expensive case. ".....", branches 26 ways immediately, before any prefix has narrowed the search. A dot at the end is cheap because the walk has already pruned to a small subtree.

Word Search II — where tries earn their place

Given a grid of letters and a list of words, find all words present in the grid (adjacent cells, no cell reused within a word).

Why the obvious approach fails

Run Word Search once per word: O(W · m · n · 4^L). With 3×10⁴ words, that's hopeless.

The waste: searching for "apple" and "apply" re-explores the identical path a-p-p-l twice.

The fix

Put all the words in a trie and walk the grid once, letting the trie prune. At each cell, if no word continues down that character, stop immediately.

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    String word = null;              // store the WHOLE word at its terminal node
}

public List<String> findWords(char[][] board, String[] words) {
    TrieNode root = new TrieNode();
    for (String w : words) {
        TrieNode cur = root;
        for (char c : w.toCharArray()) {
            int i = c - 'a';
            if (cur.children[i] == null) cur.children[i] = new TrieNode();
            cur = cur.children[i];
        }
        cur.word = w;
    }

    List<String> res = new ArrayList<>();
    for (int r = 0; r < board.length; r++) {
        for (int c = 0; c < board[0].length; c++) {
            dfs(board, r, c, root, res);
        }
    }
    return res;
}

private void dfs(char[][] board, int r, int c, TrieNode node, List<String> res) {
    if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) return;

    char ch = board[r][c];
    if (ch == '#') return;                       // already used on the CURRENT path

    TrieNode next = node.children[ch - 'a'];
    if (next == null) return;                    // *** THE PRUNE ***

    if (next.word != null) {
        res.add(next.word);
        next.word = null;                        // de-duplicate without a Set
    }

    board[r][c] = '#';                           // mark as used
    dfs(board, r + 1, c, next, res);
    dfs(board, r - 1, c, next, res);
    dfs(board, r, c + 1, next, res);
    dfs(board, r, c - 1, next, res);
    board[r][c] = ch;                            // RESTORE — this is the backtrack
}

Four techniques, each reusable

1. if (next == null) return; — the prune. This is the entire point. Without it you're doing brute force with extra steps. Most grid paths die within two or three characters because no word has that prefix.

2. Store the word at its terminal node. Instead of building the current string with a StringBuilder and appending/removing at every step, just read next.word when you arrive. Less code, no bookkeeping.

3. next.word = null after a hit — deduplication for free. If the same word is reachable by two different grid paths, the second arrival finds word == null and doesn't re-add it. O(1), no Set needed.

4. In-place '#' marking with restore. O(1) space instead of a boolean[m][n]. The restore line is what makes this backtracking rather than flood fill — the mark means "on the current path", not "seen ever". Remove the restore and you'd wrongly block cells for unrelated words. See 15 and 16 for the contrast.

Further optimization if pushed: prune the trie itself — after finding a word, if its node has no children left, remove it from its parent so that branch is never explored again.

Complexity summary

L = word length, n = number of words, d = number of wildcards.

On the Word Search II bound: it's honest but pessimistic. The trie prune means real inputs run far below it, because most grid paths die almost immediately. State the bound, then explain why practice differs — that's a more sophisticated answer than either half alone.

Recognition checklist

Reach for a trie when you see:

• "Prefix" anywhere in the problem statement.
• A set of words queried repeatedly — build once, query many times.
• Wildcard or fuzzy matching against a dictionary.
• A search that should be pruned by "no word can continue this way" — grid search, word squares, autocomplete.

Do not build a trie for a single exact-match lookup. A HashSet is simpler and equally fast. The trie only earns its complexity when prefixes are shared, or when the negative answer is what you need.