Tries

The shape: the word is the path

A hash set of words answers exactly one question well: "is this exact string present?" It is useless for "does anything here start with ca?" — you'd have to scan every key. A trie (prefix tree) fixes that by storing each character as an edge in a tree, so a word is a root-to-node path and every shared prefix is shared storage. Looking up a prefix costs O(length of the prefix), completely independent of how many words the dictionary holds.

Each node holds two things and nothing else: a map from next-character to child node, and a boolean saying "a complete word ends here." That second flag is load-bearing — without it you can't tell the stored word "do" from the mere prefix "do" inside "dog".

The structure from scratch

A Map for children beats a fixed 26-slot array: it costs nothing for sparse nodes, and it survives inputs that aren't lowercase a–z (digits, unicode, arbitrary keys). The fixed array is faster by a constant factor when the alphabet really is 26 letters, and it's worth mentioning that tradeoff out loud, but reach for the Map by default.

class TrieNode {
  constructor() {
    this.children = new Map(); // char → TrieNode
    this.isEnd = false;        // a complete stored word terminates here
  }
}

class Trie {
  constructor() { this.root = new TrieNode(); }

  // O(L) time where L = word.length, O(L) new nodes worst case
  insert(word) {
    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;
  }

  // walk as far as the string goes; returns the node or null
  _walk(str) {
    let node = this.root;
    for (const ch of str) {
      node = node.children.get(ch);
      if (!node) return null;
    }
    return node;
  }

  search(word) {
    const node = this._walk(word);
    return node !== null && node.isEnd; // reaching the node is NOT enough
  }

  startsWith(prefix) {
    return this._walk(prefix) !== null; // here reaching the node IS enough
  }
}

Cost: pay for the word length, not the dictionary size

The sorted-array column is the honest competitor people forget: sorting the dictionary puts every prefix group in a contiguous block, so binary search handles prefix queries too. The trie wins when the dictionary changes (insertions are O(L), not O(n)) and when you need to walk character-by-character while doing something else — which is exactly the Word Search II case below, and the real reason tries show up in interviews.

Autocomplete: collect everything under a prefix

Walk to the prefix node in O(P), then DFS its subtree collecting every isEnd. The cost is O(P + size of the subtree), which is proportional to the answer rather than the dictionary — that's what makes it viable at search-box latency.

function autocomplete(trie, prefix, limit = 10) {
  const start = trie._walk(prefix);
  if (!start) return [];

  const out = [];
  (function dfs(node, suffix) {
    if (out.length >= limit) return; // stop the moment we have enough
    if (node.isEnd) out.push(prefix + suffix);

    // sort keys for lexicographic order; skip the sort if insertion order is fine
    for (const ch of [...node.children.keys()].sort()) {
      dfs(node.children.get(ch), suffix + ch);
      if (out.length >= limit) return;
    }
  })(start, "");

  return out;
}

Real autocomplete wants top-k by popularity, not lexicographic order, and that changes the design: store a frequency on each terminal node, and at insert time also push the word into a small "best few in this subtree" list on every node along the path. Then a prefix query is O(P) with no DFS at all — you read the cached list off the prefix node. That precompute-on-write trade is exactly the answer expected in a "design a search suggestion service" system-design follow-up.

Wildcard search — the '.' matches any character

The "Design Add and Search Words" variant adds a dot that matches any single character. Deterministic lookup becomes a small DFS: a concrete character follows one child, a dot branches to all of them.

function searchPattern(node, word, i = 0) {
  if (i === word.length) return node.isEnd;

  const ch = word[i];
  if (ch !== ".") {
    const next = node.children.get(ch);
    return next ? searchPattern(next, word, i + 1) : false; // single deterministic step
  }

  for (const child of node.children.values()) {
    if (searchPattern(child, word, i + 1)) return true; // dot = branch over every child
  }
  return false;
}

Worst case (a query of all dots) this degenerates to visiting the whole trie, O(26^L) branching bounded by the number of nodes — but note the branching factor is the number of existing children, not 26, so on a real dictionary it collapses fast. Say that bound out loud rather than claiming O(L).

Word Break — the trie kills the substring scanning

The DP is the familiar one from the 1D DP chapter: ok[i] means "s[0..i) is fully segmentable." The naive inner loop slices s.substring(i, j) and hashes it, costing O(n² · L). Walking a trie instead reuses the previous character's work and — crucially — breaks the instant no dictionary word continues down this path.

function wordBreak(s, wordDict) {
  const root = {};
  for (const w of wordDict) { // plain objects are fine and fast when keys are chars
    let node = root;
    for (const ch of w) {
      if (!node[ch]) node[ch] = {};
      node = node[ch];
    }
    node.end = true;
  }

  const n = s.length;
  const ok = new Array(n + 1).fill(false);
  ok[0] = true; // the empty prefix is trivially segmentable

  for (let i = 0; i < n; i++) {
    if (!ok[i]) continue; // unreachable start — nothing to extend

    let node = root;
    for (let j = i; j < n; j++) {
      node = node[s[j]];
      if (!node) break; // THE win: no dictionary word starts s[i..j], abandon this start
      if (node.end) ok[j + 1] = true;
    }
  }
  return ok[n];
}

Worst case is still O(n²), but the break means the inner loop runs only as far as the longest dictionary word that actually matches — in practice a handful of characters, not n. No substrings are allocated either, which matters more than it looks on long inputs.

Word Search II — the trie prunes the backtracking

This is the problem tries exist for in interviews. Find every dictionary word hidden in a grid. Running the single-word Word Search backtracking from the backtracking chapter once per word is O(W · R · C · 4^L) and times out. The fix is to invert the loop: build one trie of all words and DFS the grid once, carrying a trie node alongside the position. The moment the path spells something no word starts with, the branch dies.

function findWords(board, words) {
  const root = {};
  for (const w of words) {
    let node = root;
    for (const ch of w) {
      if (!node[ch]) node[ch] = {};
      node = node[ch];
    }
    node.word = w; // store the word itself — no need to rebuild it from the path
  }

  const rows = board.length, cols = board[0].length;
  const found = [];

  function dfs(r, c, node) {
    const ch = board[r][c];
    const next = node[ch];
    if (!next) return; // PRUNE: no word in the dictionary continues this way

    if (next.word) {
      found.push(next.word);
      delete next.word; // de-dupe: never report the same word twice
    }

    board[r][c] = "#"; // mark visited in place, same trick as Word Search
    if (r > 0)        dfs(r - 1, c, next);
    if (r < rows - 1) dfs(r + 1, c, next);
    if (c > 0)        dfs(r, c - 1, next);
    if (c < cols - 1) dfs(r, c + 1, next);
    board[r][c] = ch; // un-choose

    // leaf pruning: this branch is exhausted, unlink it so future DFS never enters
    if (Object.keys(next).length === 0) delete node[ch];
  }

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

delete next.word rather than next.word = null matters for the pruning line below it: an assigned-null key still shows up in Object.keys, so the node would never look empty and the prune would never fire.

Advanced aside: the binary trie for maximum XOR

A trie doesn't have to be built from letters. Write each number as its 32-bit binary string and insert those — now the "alphabet" is {0, 1}, the tree is exactly 32 deep, and you can answer "which stored number XORs with x to give the largest result?" greedily. XOR gives a 1 bit exactly when the bits differ, and the high bits dominate the value, so at each level you steer toward the opposite bit if such a branch exists.

// maximum XOR of any pair — O(32n) time, O(32n) nodes, vs O(n²) brute force
function findMaximumXOR(nums) {
  const BITS = 31; // stay inside 32-bit signed range: bit 31 down to bit 0
  const root = {};

  for (const num of nums) {
    let node = root;
    for (let b = BITS; b >= 0; b--) {
      const bit = (num >> b) & 1;
      if (!node[bit]) node[bit] = {};
      node = node[bit];
    }
  }

  let best = 0;
  for (const num of nums) {
    let node = root, current = 0;
    for (let b = BITS; b >= 0; b--) {
      const bit = (num >> b) & 1;
      const want = bit ^ 1; // the opposite bit sets this position in the XOR
      if (node[want]) {
        current |= 1 << b;  // greedy: a high bit is worth more than every lower bit combined
        node = node[want];
      } else {
        node = node[bit];   // forced to match — this bit contributes 0
      }
    }
    best = Math.max(best, current);
  }
  return best;
}

The greedy step is safe for the same reason binary place value works: setting bit b contributes 2^b, which strictly exceeds the sum of every lower bit (2^b − 1). So there is never a reason to give up a high bit hoping to win low ones. The same structure, with counts stored per node, extends to "count pairs with XOR less than k" and to offline queries with a max-value constraint.

Recognizing it in an unseen problem

• The words prefix, autocomplete, dictionary, starts with, or a list of words plus something to search them against
• You're building a candidate string one character at a time (grid DFS, backtracking, DP over a string) and want to abandon it the moment no target could continue — that incremental "still a valid prefix?" check is the trie's unique ability
• Brute force is "for each of W words, scan/search the whole input" — the trie inverts it to one pass over the input carrying all W words at once
• Distinguish from a hash set: if only exact membership is ever asked, a Set is simpler, smaller and faster — don't build a trie to show off
• Distinguish from suffix structures: "any substring" questions (repeated substrings, longest common substring) want a suffix trie/automaton or hashing, not a plain prefix trie
• Bitwise pair problems — maximum XOR, XOR under a threshold — are a binary trie over 32-bit strings in disguise
• Watch the flag: isEnd is separate from "leaf," and search vs startsWith must differ by exactly that check