Tries

A trie (pronounced “try”, from retrieval) is a tree where each edge represents one character. Strings sharing a common prefix share the same path from the root. This shared-prefix property makes tries the natural data structure for autocomplete, spell-checking, IP routing (longest-prefix matching), and a cluster of hard LeetCode problems that are nearly impossible to solve efficiently with any other structure.

What Is a Trie

Each node in a trie represents one character in the path from the root. A boolean flag isEnd marks nodes where a complete word terminates. Multiple words can share prefixes — they diverge at the first differing character.

Words inserted: ["app", "apple", "ba"]

         root
        /    \
       a      b
       |      |
       p      a  [isEnd=true]  ← "ba"
       |
       p  [isEnd=true]         ← "app"
       |
       l
       |
       e  [isEnd=true]         ← "apple"

Key insight: all words starting with "app" share the nodes root → a → p → p. Searching for any prefix requires traversing only that prefix’s length — regardless of how large the dictionary is.

Why Tries Beat HashMaps for Prefix Queries

Where m = word length, n = number of words. For large dictionaries with frequent prefix queries, the trie wins by a factor of n.

TrieNode and Trie Implementation

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEnd: boolean = false;
}

class Trie {
  private root = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch)!;
    }
    node.isEnd = true;
  }

  search(word: string): boolean {
    const node = this.traverse(word);
    return node !== null && node.isEnd; // must be a complete word
  }

  startsWith(prefix: string): boolean {
    return this.traverse(prefix) !== null; // prefix exists anywhere
  }

  private traverse(s: string): TrieNode | null {
    let node = this.root;
    for (const ch of s) {
      if (!node.children.has(ch)) return null;
      node = node.children.get(ch)!;
    }
    return node;
  }
}
// insert: O(m)   search: O(m)   startsWith: O(m)   Space: O(total characters inserted)

Array-Based Children (Lowercase Letters Only)

When input is restricted to lowercase English letters, replace Map with a fixed 26-slot array. Faster constant factor, no hashing overhead:

class TrieNodeArr {
  children: (TrieNodeArr | null)[] = new Array(26).fill(null);
  isEnd = false;
}

// Index a character: ch.charCodeAt(0) - 97
// 'a' → 0, 'b' → 1, ..., 'z' → 25

Use Map-based children when the alphabet is large or unknown (Unicode, mixed case). Use the array variant for constrained alphabets — it’s what interviewers expect for LC-style problems.

LC 208: Implement Trie (Prefix Tree)

The Trie class above is the exact solution. All three operations (insert, search, startsWith) run in O(m) time where m is the word length. Space is O(total characters inserted) in the worst case with no shared prefixes.

Common mistake here: returning true from search when only a prefix exists, not a full word. The isEnd check is non-negotiable.

LC 211: Design Add and Search Words

addWord is standard trie insertion. search must handle '.' as a wildcard that matches any single character. This requires branching to all children at each dot — a DFS through the trie.

class WordDictionary {
  private root = new TrieNode();

  addWord(word: string): void {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch)!;
    }
    node.isEnd = true;
  }

  search(word: string): boolean {
    return this.dfs(this.root, word, 0);
  }

  private dfs(node: TrieNode, word: string, i: number): boolean {
    if (i === word.length) return node.isEnd;

    const ch = word[i];
    if (ch === '.') {
      // Wildcard: try every child
      for (const child of node.children.values()) {
        if (this.dfs(child, word, i + 1)) return true;
      }
      return false;
    }

    const next = node.children.get(ch);
    return next ? this.dfs(next, word, i + 1) : false;
  }
}
// addWord: O(m)
// search: O(m) typical, O(26^m) worst case with all dots — bounded by actual trie size

Interview tip: the DFS branch for '.' is where candidates stumble. Make clear that you try all children and short-circuit on the first true.

LC 212: Word Search II

Given an m×n board of characters and a list of words, find all words that can be formed by sequences of adjacent (horizontally/vertically) cells, where each cell is used at most once per word.

Why trie? A naïve approach runs DFS on the board separately for each word — O(words × 4 × 3^(L-1) × M × N). A trie lets all words share a single board traversal: walk the board once while simultaneously walking the trie.

Key pruning: after finding a word, delete the terminal node upward if it has no remaining children. This collapses exhausted branches and prevents re-finding the same word.

class WordTrieNode {
  children: Map<string, WordTrieNode> = new Map();
  word: string | null = null; // stores the complete word at terminals
}

function findWords(board: string[][], words: string[]): string[] {
  // Build trie from word list
  const root = new WordTrieNode();
  for (const w of words) {
    let node = root;
    for (const ch of w) {
      if (!node.children.has(ch)) node.children.set(ch, new WordTrieNode());
      node = node.children.get(ch)!;
    }
    node.word = w;
  }

  const rows = board.length;
  const cols = board[0].length;
  const result: string[] = [];

  function dfs(r: number, c: number, node: WordTrieNode): void {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    const ch = board[r][c];
    if (ch === '#' || !node.children.has(ch)) return; // visited or no trie path

    const next = node.children.get(ch)!;

    if (next.word !== null) {
      result.push(next.word);
      next.word = null; // prevent duplicates without a visited set
    }

    board[r][c] = '#'; // mark visited for this DFS path
    dfs(r + 1, c, next);
    dfs(r - 1, c, next);
    dfs(r, c + 1, next);
    dfs(r, c - 1, next);
    board[r][c] = ch; // restore cell

    // Prune: remove this trie node if it's now a dead end
    if (next.children.size === 0 && next.word === null) {
      node.children.delete(ch);
    }
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      dfs(r, c, root);
    }
  }

  return result;
}
// Time: O(M × 4 × 3^(L-1)) where M = board cells, L = max word length
//   — each DFS starts at a cell, has 4 initial directions, then 3 subsequent (can't backtrack)
//   — pruning makes practical performance significantly better
// Space: O(N × L) for the trie, O(L) recursion stack

Why pruning matters: after finding “apple”, the path a→p→p→l→e is exhausted. Removing it prevents re-visiting those characters on future DFS calls, shrinking the trie progressively. On a dense board with many words, this can reduce runtime by 50%+.

Autocomplete Systems

A production autocomplete (Google search bar, Yelp search, VS Code IntelliSense) layers three things on top of a basic trie:

class AutocompleteNode {
  children: Map<string, AutocompleteNode> = new Map();
  isEnd = false;
  freq = 0;            // how many times this word was searched/used
  topSuggestions: string[] = []; // cached top-3 completions for this prefix
}

Frequency ranking: when a user selects a suggestion, walk the trie for that word and increment freq at the terminal node. Suggestions are ranked by freq descending.

Caching top-K: storing the top-K results at every prefix node gives O(1) retrieval at query time (at the cost of O(K × prefix_length) update time when a new word is inserted). This is the classic time/space tradeoff.

Distributed architecture at scale: a single trie for all of Google’s queries wouldn’t fit in one machine’s memory. Companies shard tries by prefix — for example by first character, or by first two characters. A query router sends each prefix to the correct shard. Each shard fits comfortably in memory on one server and can be replicated for fault tolerance. Invalidating cached topSuggestions after a viral new query means updating every prefix node along that word’s path — typically handled asynchronously via a message queue.

Compressed Trie (Radix Tree)

A standard trie wastes nodes on long non-branching chains. A radix tree (compressed trie) merges runs of single-child nodes into one node that stores an entire substring:

Standard trie for ["interview", "interesting"]:
  i → n → t → e → r → v → i → e → w    (terminal)
                        → e → s → t → i → n → g  (terminal)

Radix tree:
  "inter" → v → "iew"   (terminal)
           → "esting"   (terminal)

For a sparse trie with a small set of long strings, a radix tree reduces node count from O(total characters) to O(number of words). The Linux kernel’s IP routing table and many DNS implementations use radix trees for this reason.

For dense tries (most nodes have multiple children, as in a full dictionary), the savings are minimal and the added implementation complexity is rarely worth it in interviews.

Trie vs HashMap: Full Tradeoff Table

Reach for a trie when: prefix queries, autocomplete, spell-checking, wildcard matching, or storing strings where common prefixes should share memory. Reach for a HashMap when: only exact lookups are needed and prefix operations are irrelevant.

Space Complexity

Let N = number of words, M = average word length, A = alphabet size.

• Worst case (no shared prefixes): O(A × N × M) nodes with array-based children, O(N × M) with Map-based
• Best case (all words share a prefix): O(A × M_max) nodes, where M_max is the longest word
• Typical case: between the two — depends on how much sharing exists

For lowercase English with array children: each TrieNodeArr uses 26 pointers (208 bytes on a 64-bit system). A million-word dictionary with average 10-character words and no sharing would consume ~2 GB. Real dictionaries have substantial sharing, reducing this dramatically. Map-based nodes only allocate for actual children.

Common Interview Mistakes

1. Forgetting isEnd — search("app") returns false if only "apple" was inserted. The isEnd check on the terminal node is mandatory.

2. Not handling the empty string — insert("") should set root.isEnd = true. search("") should return root.isEnd. Most implementations silently break on empty input.

3. Mutating the board without restoring in Word Search II — always restore board[r][c] after each DFS call. Missing this causes one path’s visited markers to bleed into sibling paths.

4. Skipping trie pruning in Word Search II — without removing exhausted branches, the trie never shrinks and you may TLE on large boards with many short words.

5. Confusing search with startsWith — search("app") requires isEnd = true at the 'p' node; startsWith("app") only requires the path to exist.

6. Choosing array children for non-lowercase inputs — if the problem involves uppercase letters, digits, or arbitrary Unicode, a Map is required. Hardcoding array size 26 on a mixed-case problem is a silent bug.