Trie

A Trie stores strings character by character in a tree of nodes, giving O(L) insert and search for a word of length L regardless of how many words are stored.

• Replaces O(N×L) scanning of all stored words with O(L) lookup by following a single path through the tree
• Two modes: exact word search (check the end-of-word flag at the last node) and prefix search (verify the path exists without checking end-of-word)
• Reach for it when problems involve word dictionaries, prefix matching, or searching a board for multiple words at once

Quick Revision - Must Do Problems

If short on time, solve only these. They cover ~90% of Trie patterns.

Practice Tips

How to Identify a Trie Problem

• "Insert words into a dictionary and search for them" or "implement an autocomplete system"
• "Find all words on a board from a given word list" — searching for many words at once
• "Count words with a given prefix" or "find the shortest unique prefix"
• HashMap alone doesn't work because prefix queries need structural traversal

Trie vs. Other Techniques

Interview Approach

1. Define TrieNode: children array of size 26 (for lowercase English) + isEnd boolean
2. Insert: walk from root character by character, create nodes as needed, mark isEnd = true at the last node
3. Search: walk from root, return false if any child is missing, check isEnd at the end
4. StartsWith: same as search but return true without checking isEnd
5. For wildcard '.': at that position, try every non-null child recursively (DFS)
6. For board search: store the matched word string on the Trie node itself — avoids reconstructing the word during DFS and simplifies deduplication

2 Main Patterns

Pattern 1: Basic Trie (Insert / Search / Prefix)

Copyclass TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd = false;
}
// Insert: root → last char, create nodes, set isEnd = true
// Search: root → last char, verify each child exists, return node.isEnd
// StartsWith: same as search, return true (skip isEnd check)

Pattern 2: DFS on Trie (Wildcard / Board Search)

Copy// Wildcard '.': at the wildcard position, recurse into every non-null child
// Board search: advance trie node and board position together;
//               prune the entire branch early when the trie child is null

General Templates

TrieNode + Core Operations

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

class Trie {
    private TrieNode root = new TrieNode();

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

    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                return false;
            }
            node = node.children[idx];
        }
        return node.isEnd;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                return false;
            }
            node = node.children[idx];
        }
        return true;
    }
}

Wildcard DFS Template

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

Board Search Template (Trie + Backtracking)

Copy// TrieNode stores the word string instead of just isEnd — avoids reconstruction
class TrieNode {
    TrieNode[] children = new TrieNode[26];
    String word = null;  // non-null at the end of a complete word
}

private void dfs(char[][] board, int r, int c, TrieNode node, List<String> result) {
    if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) {
        return;
    }
    char ch = board[r][c];
    if (ch == '#' || node.children[ch - 'a'] == null) {
        return;  // pruned
    }
    node = node.children[ch - 'a'];
    if (node.word != null) { result.add(node.word); node.word = null; } // deduplicate
    board[r][c] = '#';  // mark visited
    dfs(board, r+1, c, node, result);
    dfs(board, r-1, c, node, result);
    dfs(board, r, c+1, node, result);
    dfs(board, r, c-1, node, result);
    board[r][c] = ch;   // restore
}

Problem 1: Implement Trie ⭐ MUST DO

Implement a Trie data structure supporting insert, search, and startsWith.

Example:

Copyinsert("apple")
search("apple")    →  true
search("app")      →  false
startsWith("app")  →  true
insert("app")
search("app")      →  true

Key Insight:

• Each node has an array of 26 children (one per letter) and a boolean end-of-word flag. Insert walks from root creating nodes as needed. Search walks the same path — if any node is missing the word doesn't exist; if all nodes exist, check the end-of-word flag. StartsWith is identical to search but skips the final flag check.

Solution:

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

class Trie {
    private TrieNode root = new TrieNode();

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

    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                return false;
            }
            node = node.children[idx];
        }
        return node.isEnd;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                return false;
            }
            node = node.children[idx];
        }
        return true;
    }
}

Complexity:

Problem 2: Add and Search Words ⭐ MUST DO

Design a data structure that supports adding words and searching with '.' as a wildcard that matches any letter.

Example:

CopyaddWord("bad"), addWord("dad"), addWord("mad")
search("pad")  →  false
search("bad")  →  true
search(".ad")  →  true
search("b..")  →  true

Key Insight:

• Same Trie structure as Implement Trie, but search must handle '.' wildcards. When '.' is encountered, branch into every non-null child recursively. This turns search into a DFS that explores all matching paths. Use a helper method that takes the current Trie node and character index.

Solution:

Copyclass WordDictionary {
    private TrieNode root = new TrieNode();

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

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

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

Complexity:

Problem 3: Word Search II ⭐ MUST DO

Given an m×n board and a list of words, return all words from the list that exist on the board. A word is formed by adjacent cells (horizontal/vertical, no reuse).

Example:

Copyboard = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

Key Insight:

• Running a separate DFS for each word is O(W × M × N × 4^L) — too slow when W is large. Build a Trie from the word list first. Then run one DFS from each board cell, advancing through the Trie simultaneously. If the current Trie child is null, prune the entire branch — the board prefix can't form any word. Store the complete word string on the Trie node to avoid reconstructing it during DFS. Set node.word = null after adding to the result to deduplicate.

Solution:

Copyclass TrieNode {
    TrieNode[] children = new TrieNode[26];
    String word = null;
}

public List<String> findWords(char[][] board, String[] words) {
    TrieNode root = new TrieNode();
    for (String w : words) {                    // build trie from word list
        TrieNode node = root;
        for (char c : w.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new TrieNode();
            }
            node = node.children[idx];
        }
        node.word = w;
    }

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

private void dfs(char[][] board, int r, int c, TrieNode node, List<String> result) {
    if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) {
        return;
    }
    char ch = board[r][c];
    if (ch == '#' || node.children[ch - 'a'] == null) {
        return; // pruned
    }
    node = node.children[ch - 'a'];
    if (node.word != null) { result.add(node.word); node.word = null; } // found + dedupe
    board[r][c] = '#';   // mark visited
    dfs(board, r+1, c, node, result);
    dfs(board, r-1, c, node, result);
    dfs(board, r, c+1, node, result);
    dfs(board, r, c-1, node, result);
    board[r][c] = ch;    // restore
}

Complexity:

Quick Reference Table

When to Use Each Pattern

Basic Trie (Insert / Search / Prefix)

• Any problem that requires both exact-word lookup and prefix-based lookup
• When a HashSet would work for exact search but the problem also asks about prefixes
• "Design" problems: autocomplete, word suggestion, prefix count

Wildcard DFS

• Pattern matching where '.' or '?' can match any character
• Switch from iterative search to recursive DFS at the wildcard position
• Still O(L) for inputs with no wildcards; only slows down proportionally to wildcard count

Trie + Board Backtracking

• Board + word list problems — classic "find all words that exist on the board"
• Key advantage over per-word DFS: one traversal, shared prefix pruning across all words
• Store the matched word on the Trie node to avoid building it character by character during DFS

Common Mistakes to Avoid

Build Mistakes

1. Using isEnd for board search — when DFS finds a word, you can't tell which word it was without walking back. Store the word string on the node directly (node.word = w) so you can add it to results immediately
2. Forgetting startsWith skips isEnd check — startsWith("app") must return true even if only "apple" was inserted; only search checks isEnd

DFS Mistakes

3. Not deduplicating in Word Search II — if the same word appears twice on the board, the DFS will find it twice. After adding to results, set node.word = null to prevent adding it again
4. Forgetting to restore the board cell — always restore board[r][c] = ch after the recursive DFS calls return; forgetting this corrupts the board for other starting cells
5. Not pruning on null trie child — the key optimization in Word Search II is returning immediately when node.children[ch - 'a'] == null; without this the code is O(M×N×4^L) per word