Trie

At a glance

The instinct

A hash set answers "is this exact word present?" but is blind to prefixes: to find every word starting with "app" you would scan the whole set. A trie flips the storage around - each edge is one character, each node is a prefix, and words that begin the same way literally share a path. Asking about a prefix becomes walking down that path, which costs only the prefix length, no matter how many words are stored.

The same idea works on bits: a binary trie stores numbers bit by bit from the most significant end, which turns "maximum XOR pair" into a greedy walk.

Recognise it

Not this pattern if...

• You only need exact-match lookups - a HashSet<String> is simpler.
• You must match one pattern inside a long text - KMP or rolling hash fits better.
• The "prefix" is numeric (prefix sums over an array) - unrelated despite the name.

Memory hack

Analogy - a phone's contact search. Type M and the list shrinks to names starting with M; type Ma and it shrinks again. The phone never rescans the whole contact list - it simply follows the branch you are typing. Every name that starts with "Ma" lives under the same branch.

Say it out loud in the interview:

1. "Lots of words with shared prefixes - I'll build a trie: node = children[26] + isEnd (or a stored word)."
2. "Insert and lookup walk one character per step - O(L) each."
3. "For wildcards or grids, I DFS through the trie and prune the moment a child is missing."

How it works

Insert cat, car, cart, dog. The prefix ca is stored once and branches into t and r.

flowchart TD
  R(("root")) --> C["c"]
  R --> D["d"]
  C --> A["a"]
  A --> T["t (end: cat)"]
  A --> R2["r (end: car)"]
  R2 --> T2["t (end: cart)"]
  D --> O["o"]
  O --> G["g (end: dog)"]

• search("car") walks c-a-r and finds the end flag: true.
• search("ca") walks c-a but the flag is off: false; startsWith("ca") is true.
• In Word Search II, the grid DFS carries a trie node instead of a string. Moving onto a letter with no matching child stops that branch immediately, so all dictionary words are searched in a single sweep of the board.

Java template

import java.util.*;

class Trie {
    private static class Node {
        Node[] next = new Node[26];   // swap for HashMap<Character, Node> on large alphabets
        boolean isEnd;                // or: String word; int count; int prefixCount;
    }

    private final Node root = new Node();

    void insert(String word) {
        Node cur = root;
        for (char ch : word.toCharArray()) {
            int i = ch - 'a';
            if (cur.next[i] == null) cur.next[i] = new Node();
            cur = cur.next[i];
        }
        cur.isEnd = true;
    }

    boolean search(String word) { Node n = walk(word); return n != null && n.isEnd; }

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

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

    // Wildcard search: '.' matches any single letter.
    boolean match(String pattern) { return dfs(root, pattern, 0); }

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

// Binary trie: maximum XOR of any two numbers (non-negative ints).
class BitTrie {
    private final int[][] next;
    private int count = 1;                                      // node 0 is the root

    BitTrie(int n) { next = new int[31 * n + 1][2]; }           // 31 bits per number at most

    void insert(int x) {
        int cur = 0;
        for (int b = 30; b >= 0; b--) {
            int bit = (x >> b) & 1;
            if (next[cur][bit] == 0) next[cur][bit] = count++;
            cur = next[cur][bit];
        }
    }

    int bestXor(int x) {                                        // call after at least one insert
        int cur = 0, res = 0;
        for (int b = 30; b >= 0; b--) {
            int bit = (x >> b) & 1, want = bit ^ 1;
            if (next[cur][want] != 0) { res |= 1 << b; cur = next[cur][want]; }
            else cur = next[cur][bit];
        }
        return res;
    }
}

Complexity

Array children are fast but memory hungry (26 references per node); a HashMap per node saves memory for sparse or Unicode alphabets at a constant-factor speed cost.

Variations

• Classic dictionary - insert/search/prefix. Implement Trie (Prefix Tree).
• Wildcard DFS - branch on .. Design Add and Search Words Data Structure.
• Grid + trie backtracking - store the full word at its end node, clear it once found, prune empty branches. Word Search II.
• Autocomplete / top suggestions - walk the typed prefix, then gather up to k words in lexicographic order (or keep a small sorted list at each node). Search Suggestions System.
• Prefix chain - every prefix must itself be a word. Longest Word in Dictionary (BFS/DFS only through end-flagged nodes).
• Bitwise trie - greedy opposite-bit walk. Maximum XOR of Two Numbers in an Array.
• Counting trie - store prefixCount at each node for "how many words start with...".

Common mistakes

• Allocating a new root (or a new Node) inside every call, so inserts never accumulate.
• Hard-coding ch - 'a' when input can contain uppercase letters, digits or other symbols.
• In Word Search II, not marking the board cell as visited during DFS, or reporting the same word twice - null out the stored word after adding it.
• Rebuilding strings with + at every DFS step instead of storing the word at the terminal node (quadratic garbage).
• For the bit trie, iterating from the least significant bit - the greedy choice only works from the highest bit downward.

All practice problems

6 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.