Tries (Prefix Trees) Explained

A trie (pronounced "try") is a tree where each node stores one character and its children are the possible next characters. Words that share a prefix also share nodes, which makes prefix search as fast as a lookup. Tries power autocomplete, spell check, and many word-search interview problems.

Anatomy of a Trie

Inserting cat, car and dog shares the ca prefix. Each node marks whether a word ends there:

graph TD
    R["root"] --> C["c"]
    C --> A["a"]
    A --> T["t *"]
    A --> R2["r *"]
    R --> D["d"]
    D --> O["o"]
    O --> G["g *"]
    style R fill:#D97A2B,stroke:#B86418,color:#fff

The Insert-Search-StartsWith Template

Almost every trie problem reuses this node design: an array (or map) of children plus a boolean flag.

class TrieNode {
  children: (TrieNode | undefined)[] = new Array(26);
  isEnd = false;
}

class Trie {
  private root = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      const idx = ch.charCodeAt(0) - 97;
      if (!node.children[idx]) node.children[idx] = new TrieNode();
      node = node.children[idx]!;
    }
    node.isEnd = true;
  }

  search(word: string): boolean {
    const node = this.find(word);
    return !!node && node.isEnd;
  }

  startsWith(prefix: string): boolean {
    return !!this.find(prefix);
  }

  private find(key: string): TrieNode | undefined {
    let node: TrieNode | undefined = this.root;
    for (const ch of key) {
      node = node.children[ch.charCodeAt(0) - 97];
      if (!node) return undefined;
    }
    return node;
  }
}

All three operations run in O(L) where L is the word length, independent of how many words are stored.

Beyond the Basics: Counts and Word Retrieval

Two upgrades make tries interview-ready. A count field tracks how many words pass through a node, which is the key to ranking autocomplete suggestions. A DFS from any node collects every complete word below it:

function collect(node: TrieNode, prefix: string, out: string[]): void {
  if (node.isEnd) out.push(prefix);
  for (let i = 0; i < 26; i++) {
    const child = node.children[i];
    if (child) collect(child, prefix + String.fromCharCode(97 + i), out);
  }
}
// collect(root, "", words) returns all stored words

Real-World Uses

• Autocomplete / typeahead: navigate to the prefix node, then DFS for the top K words by count.
• Spell check: insert the dictionary, search each candidate word.
• Word Search (grid): hold a trie of the dictionary and DFS the board, pruning any path that is not a trie prefix — the classic optimized solution.
• Longest common prefix: walk children while there is exactly one child and no early end.
• IP routing: CIDR prefixes map naturally onto a binary trie.

Word Search with a Trie

For the LeetCode word-search (board) problem, insert all words into a trie, then for every cell DFS the board and only recurse into neighbors that continue a valid prefix. The trie prunes the search space so hard that the solution passes in time.

When to Reach for a Trie vs Alternatives

• Hash map: best for exact lookups; cannot answer prefix queries without scanning everything.
• Sorted array + binary search: great for static dictionaries; lower_bound can emulate prefix search.
• Radix (compressed) trie: merges single-child chains; saves space for large alphabets but is overkill for interviews.

Common Mistakes

• Forgetting the isEnd flag : without it, search("app") returns true even if only apple was inserted.
• Hardcoding 26 for inputs with spaces, digits, or uppercase, instead of using a map.
• Not checking child === undefined before dereferencing during startsWith.
• Re-examining the whole board for each word in word search, instead of one trie pass.
• Memory panic : a full 26-slot array per node is fine for ≤2,000 words; only switch to map storage for big alphabets.

Frequently Asked Questions

Related Tutorials

• Hash Maps : the classic alternative for exact lookups.
• Backtracking : the DFS that walks a trie during word search.
• Trees and Graphs : trie internals are just trees.
• Trie practice problems : company-tagged questions.