🔡 Trie

A learning sheet — a tree whose edges are characters. It answers prefix questions in O(L), no matter how many words you've stored.

🧠 1 · How to think (and invent it)

A trie stores strings by their shared prefixes. Each node owns a map of child characters; walking a word's letters from the root traces (or builds) a path, and a boolean isEnd flags where real words finish. Every operation — insert, search, prefix-check — is one walk down the word: O(L), completely independent of how many words are stored.

Watch it get invented — a prefix-searchable dictionary

1. Start with a hash set. It answers "is X a word?" in O(L) — but "is X a prefix of some word?" forces a scan of every entry: O(N·L).
2. The leap. Words that share a prefix should share storage. Lay them in a tree keyed by character; common prefixes become a single shared path that branches only where the words diverge.
3. The two queries fall out. search(w) = walk w; it's a word iff the path exists and ends on isEnd. startsWith(p) = walk p; true iff the path exists at all.
4. Payoff. O(L) per op regardless of N, and prefixes are stored once.

🎯 2 · Attack plan

🔎 3 · Recognition map

🧩 4 · The five core patterns

Node throughout: { children: Map<char, Node>, isEnd: boolean }. Each pattern: a one-liner, a 🔑 invariant, a template, a 🎤 interview lens.

4.1 · Mechanics — insert / search / startsWith

“Walk the word; create missing children on insert, follow them on lookup.”

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

class Trie {
  root = new TrieNode();

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

  walk(s: string): TrieNode | null {     // shared helper: follow a string; null if the path breaks
    let node = this.root;
    for (const c of s) {
      const next = node.children.get(c);
      if (!next) return null;
      node = next;
    }
    return node;
  }

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

  startsWith(prefix: string): boolean {
    return this.walk(prefix) !== null;
  }
}

The escalation interviewers reach for: swap the isEnd boolean for two counts per node — and erase plus "how many words/prefixes?" become one-line decrements (LC 1804, Implement Trie II).

// Trie II — counts make delete + "how many?" trivial
class CTrieNode { children = new Map<string, CTrieNode>(); ends = 0; passing = 0; }

class CountingTrie {
  root = new CTrieNode();
  insert(word: string): void {
    let node = this.root;
    for (const c of word) {
      if (!node.children.has(c)) node.children.set(c, new CTrieNode());
      node = node.children.get(c)!;
      node.passing++;                              // +1 word runs through this node
    }
    node.ends++;                                   // +1 word ends here
  }
  private walk(s: string): CTrieNode | null {
    let node = this.root;
    for (const c of s) {
      const next = node.children.get(c);
      if (!next) return null;
      node = next;
    }
    return node;
  }

  countWordsEqualTo(word: string): number { return this.walk(word)?.ends ?? 0; }
  countWordsStartingWith(pre: string): number { return this.walk(pre)?.passing ?? 0; }

  erase(word: string): void {                      // assumes the word was inserted
    let node = this.root;
    for (const c of word) {
      node = node.children.get(c)!;
      node.passing--;
    }
    node.ends--;                                   // (a real impl may also prune dead nodes)
  }
}

4.2 · Prefix queries — autocomplete

“Walk to the prefix node, then DFS everything beneath it.”

Setup: the subtree rooted at the prefix node contains exactly the words sharing that prefix — collect them with a DFS.

// All stored words that start with `prefix` (uses Trie.walk from §4.1)
function wordsWithPrefix(trie: Trie, prefix: string): string[] {
  const start = trie.walk(prefix);       // the node where the prefix ends
  if (!start) return [];                 // prefix not present → no completions
  const out: string[] = [];
  function dfs(node: TrieNode, suffix: string): void {
    if (node.isEnd) out.push(prefix + suffix);
    for (const [c, child] of node.children) {
      dfs(child, suffix + c);
    }
  }
  dfs(start, '');
  return out;
}

The FAANG version of this pattern (a top Amazon question): as the user types each letter, return the 3 lexicographically-smallest completions. Trick: sort once, then have every node remember the first ≤3 words inserted through it — queries become a plain walk.

// Search Suggestions System (1268) — top-3 completions per typed prefix
class SNode {
  children = new Map<string, SNode>();
  suggestions: string[] = [];            // the ≤3 lexicographically-smallest words through here
}

function suggestedProducts(products: string[], searchWord: string): string[][] {
  products.sort();                                 // sort once → insertion order = lexicographic
  const root = new SNode();
  for (const word of products) {
    let node = root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new SNode());
      node = node.children.get(ch)!;
      if (node.suggestions.length < 3) node.suggestions.push(word);   // first 3 = smallest 3
    }
  }
  const out: string[][] = [];
  let node: SNode | null = root;
  for (const ch of searchWord) {                   // type the word letter by letter
    node = node ? (node.children.get(ch) ?? null) : null;   // dead prefix stays dead
    out.push(node ? node.suggestions : []);
  }
  return out;
}

4.3 · Wildcard search (. matches any)

“On a literal, follow one child; on a dot, try them all.”

Setup: a normal walk can't handle . because it could match several children — so the walk becomes a branching DFS that recurses into every child whenever it sees a dot.

// Add and Search Word (211) — '.' matches any single character
class WordDictionary {
  root = new TrieNode();

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

  search(word: string): boolean {
    function dfs(node: TrieNode, i: number): boolean {
      if (i === word.length) return node.isEnd;
      const c = word[i];
      if (c === '.') {                              // wildcard → try every child
        for (const child of node.children.values()) {
          if (dfs(child, i + 1)) return true;
        }
        return false;
      }
      const next = node.children.get(c);            // literal → one definite child
      if (!next) return false;
      return dfs(next, i + 1);
    }
    return dfs(this.root, 0);
  }
}

4.4 · Trie as a pruner (grid / word break)

“Drive one DFS by the trie — abandon any path that isn't a live prefix.”

Setup: instead of searching the grid once per word, build a trie of all words and run a single DFS; at each cell, only continue if the trie has that character as a child. The trie collapses many searches into one and prunes dead ends instantly.

// Word Search II (212) — all dictionary words found in the board
class WNode { children = new Map<string, WNode>(); word: string | null = null; }

function findWords(board: string[][], words: string[]): string[] {
  const root = new WNode();
  for (const w of words) {                       // build the trie; tag each end with its full word
    let node = root;
    for (const c of w) {
      if (!node.children.has(c)) node.children.set(c, new WNode());
      node = node.children.get(c)!;
    }
    node.word = w;
  }

  const out: string[] = [];
  const R = board.length, C = board[0].length;

  function dfs(r: number, c: number, node: WNode): void {
    const ch = board[r][c];
    const child = node.children.get(ch);
    if (!child) return;                          // PRUNE: not a live prefix
    if (child.word) {                            // a complete dictionary word ends here
      out.push(child.word);
      child.word = null;                         // dedup: collect each word once
    }
    board[r][c] = '#';                           // mark visited
    for (const [dr, dc] of [[0, 1], [0, -1], [1, 0], [-1, 0]]) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < R && nc >= 0 && nc < C && board[nr][nc] !== '#') {
        dfs(nr, nc, child);
      }
    }
    board[r][c] = ch;                            // restore (backtrack)
  }

  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) {
      dfs(r, c, root);
    }
  }
  return out;
}

4.5 · Bit trie — XOR greedily

“Store numbers as bit-paths; to maximize XOR, walk choosing the opposite bit.”

Setup: insert each number's bits MSB→LSB into a binary trie. To maximize a XOR b, for each a walk the trie always preferring the opposite bit (which sets that XOR bit to 1) when it exists.

// Maximum XOR of Two Numbers in an array (421) — 31-bit ints, bits 30…0
type BitNode = { [b in 0 | 1]?: BitNode };

function findMaximumXOR(nums: number[]): number {
  const root: BitNode = {};
  for (const num of nums) {                      // insert bits MSB → LSB
    let node = root;
    for (let b = 30; b >= 0; b--) {
      const bit = ((num >> b) & 1) as 0 | 1;
      node = node[bit] ??= {};
    }
  }
  let best = 0;
  for (const num of nums) {
    let node = root;
    let cur = 0;
    for (let b = 30; b >= 0; b--) {
      const bit = ((num >> b) & 1) as 0 | 1;
      const want = (bit ^ 1) as 0 | 1;           // greedily seek the OPPOSITE bit
      if (node[want]) {
        cur |= (1 << b);                         // opposite exists → this XOR bit is 1
        node = node[want]!;
      } else {
        node = node[bit]!;                       // same-bit branch must exist (paths are full depth)
      }
    }
    best = Math.max(best, cur);
  }
  return best;
}

⏱️ 5 · Complexity

⚠️ 6 · Pitfalls — and the test that catches each

// 642 Design Search Autocomplete System — every node keeps sentence → count for everything passing through it
type TNode = { kids: Map<string, TNode>; counts: Map<string, number> };
class AutocompleteSystem {
  private root: TNode = { kids: new Map(), counts: new Map() };
  private cur: TNode | null; private typed = '';
  constructor(sentences: string[], times: number[]) { this.cur = this.root; sentences.forEach((s, i) => this.add(s, times[i])); }
  private add(s: string, t: number) {
    let n = this.root;
    for (const ch of s) {
      if (!n.kids.has(ch)) n.kids.set(ch, { kids: new Map(), counts: new Map() });
      n = n.kids.get(ch)!; n.counts.set(s, (n.counts.get(s) ?? 0) + t);
    }
  }
  input(c: string): string[] {
    if (c === '#') { this.add(this.typed, 1); this.typed = ''; this.cur = this.root; return []; }
    this.typed += c;
    this.cur = this.cur ? this.cur.kids.get(c) ?? null : null;          // once off the trie, stay off until '#'
    if (!this.cur) return [];
    return [...this.cur.counts].sort((a, b) => b[1] - a[1] || (a[0] < b[0] ? -1 : 1)).slice(0, 3).map(e => e[0]);
  }
}

// 336 Palindrome Pairs — split every word; a palindromic half needs the reverse of the other half to exist
function palindromePairs(words: string[]): number[][] {
  const idx = new Map(words.map((w, i) => [w, i] as [string, number]));
  const isPal = (s: string) => { let l = 0, r = s.length - 1; while (l < r) if (s[l++] !== s[r--]) return false; return true; };
  const rev = (s: string) => s.split('').reverse().join('');
  const res: number[][] = [];
  words.forEach((w, i) => {
    for (let k = 0; k <= w.length; k++) {
      const left = w.slice(0, k), right = w.slice(k);
      if (isPal(left)) { const j = idx.get(rev(right)); if (j !== undefined && j !== i) res.push([j, i]); }                    // rev(right) + w
      if (right.length > 0 && isPal(right)) { const j = idx.get(rev(left)); if (j !== undefined && j !== i) res.push([i, j]); } // w + rev(left)  (right.length > 0 avoids double counting)
    }
  });
  return res;
}

// 1032 Stream of Characters — REVERSED-word trie, walk newest → oldest
class StreamChecker {
  private root: any = {}; private buf: string[] = []; private maxLen = 0;
  constructor(words: string[]) {
    for (const w of words) {
      this.maxLen = Math.max(this.maxLen, w.length);
      let n = this.root;
      for (let i = w.length - 1; i >= 0; i--) n = n[w[i]] ??= {};
      n.end = true;
    }
  }
  query(c: string): boolean {
    this.buf.push(c); if (this.buf.length > this.maxLen) this.buf.shift();
    let n = this.root;
    for (let i = this.buf.length - 1; i >= 0; i--) {
      n = n[this.buf[i]];
      if (!n) return false;
      if (n.end) return true;                                             // ANY suffix that is a word counts
    }
    return false;
  }
}

📊 Coverage — pattern → LeetCode (medium & hard)

Own each pattern and these are in range. Bold = Hard tier.

✅ 7 · Self-check

Cover the right column (blurred — hover/tap to reveal). Say your answer out loud first.

Write these cold (no peeking)

• mechanics Trie (insert / search / startsWith)
• prefix wordsWithPrefix (walk + DFS) · suggestedProducts (1268)
• wildcard WordDictionary (addWord + .-search DFS)
• grid findWords (trie pruning)
• bit findMaximumXOR

For each: write "what does isEnd/the trie node mean here?" as a comment before the code.