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
  }
}

Dry run: inserting "car", "cat", "do", "dog" — the diagram above

"car" and "cat" only ever create one new node (t) because insert's children.has(ch) check reuses the existing c→a path — that sharing is the whole point of a trie. search("d") and startsWith("do") both walk to a real node; the only reason they'd disagree on the same input is the isEnd check, which is exactly the line search has and startsWith doesn't.

Array children, Map children, and the radix trie

The Map in each node is a default, not a law. When the alphabet is fixed and small (lowercase letters, digits, DNA bases) a node can hold a plain array with one slot per letter, indexed by word.charCodeAt(i) - 97. A child lookup becomes an array read with no hashing, and a node has a fixed shape, which helps the engine.

class ArrayTrieNode {
  constructor() {
    this.children = new Array(26).fill(null); // slot 0 is "a", slot 25 is "z"
    this.isEnd = false;
  }
}

class ArrayTrie {
  constructor() { this.root = new ArrayTrieNode(); }

  insert(word) {
    let node = this.root;
    for (let i = 0; i < word.length; i++) {
      const slot = word.charCodeAt(i) - 97;
      if (node.children[slot] === null) node.children[slot] = new ArrayTrieNode();
      node = node.children[slot];
    }
    node.isEnd = true;
  }

  search(word) {
    let node = this.root;
    for (let i = 0; i < word.length; i++) {
      node = node.children[word.charCodeAt(i) - 97];
      if (node === null) return false;
    }
    return node.isEnd;
  }
}

With a Map, a node that has one child costs one entry. With the array, the same node still pays for 26, which dominates memory for long, unshared words. A mistyped input such as "A" gives slot -32, and children[-32] is undefined, not null, so the === null test lets it through into a crash. Say the tradeoff, then pick the Map unless you were told the alphabet.

Long unshared words are exactly where a plain trie wastes nodes: a word stored alone becomes a chain of single-child nodes. A radix trie (compressed trie, Patricia trie) collapses every such chain into one edge that carries a string label. Every non-root node then either ends a word or has at least two children, which bounds the whole tree at about 2n nodes for n words, whatever the word lengths.

function commonPrefixLength(a, b) {
  let i = 0;
  while (i < a.length && i < b.length && a[i] === b[i]) i++;
  return i;
}

class RadixNode {
  constructor() {
    this.edges = new Map(); // first character of the label → { label, node }
    this.isEnd = false;
  }
}

class RadixTrie {
  constructor() { this.root = new RadixNode(); }

  insert(word) {
    let node = this.root, rest = word;
    while (rest.length > 0) {
      const edge = node.edges.get(rest[0]);
      if (!edge) {                                     // no edge starts this way: one new edge holds the whole rest
        const leaf = new RadixNode();
        leaf.isEnd = true;
        node.edges.set(rest[0], { label: rest, node: leaf });
        return;
      }
      const k = commonPrefixLength(edge.label, rest);
      if (k < edge.label.length) {                     // the label only partly matches: split it at k
        const middle = new RadixNode();
        middle.edges.set(edge.label[k], { label: edge.label.slice(k), node: edge.node });
        edge.label = edge.label.slice(0, k);
        edge.node = middle;
      }
      node = edge.node;
      rest = rest.slice(k);
    }
    node.isEnd = true;
  }

  search(word) {
    let node = this.root, rest = word;
    while (rest.length > 0) {
      const edge = node.edges.get(rest[0]);
      if (!edge || !rest.startsWith(edge.label)) return false;
      node = edge.node;
      rest = rest.slice(edge.label.length);
    }
    return node.isEnd;
  }
}

Dry run: insert "car", then "cat", then "do"

The splitting step is the whole difficulty; searching is the same walk as before, comparing a whole label with startsWith instead of one character. Costs stay O(L) character comparisons per operation. A slice that copies would make the string version O(L²) in the worst case, and although V8 shares the memory of long slices, walking by index is O(L) by construction. In an interview you are almost never asked to write this; knowing it exists, and why it saves memory, is the point.

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.

Counting inside the trie: prefix counts and Map Sum

A node can carry any number that is defined by "all words below me". Store at each node the total value of the words that pass through it, and the answer to "what is the total of everything with this prefix" is the number on the prefix node: O(prefix length), no subtree walk. The design question Map Sum asks for exactly that: insert(key, val) sets a key to a value (replacing an old one), and sum(prefix) returns the total of all values whose key starts with the prefix.

The replacement rule is the trap. Re-inserting a key must not add its new value on top of the old; it must add the difference. Keep a side map of each key's current value, compute delta = val - old, and add the delta at every node on the key's path.

class MapSum {
  constructor() {
    this.root = { sum: 0, children: new Map() };
    this.values = new Map(); // key → its current value, so a replacement can be turned into a delta
  }

  insert(key, val) {
    const delta = val - (this.values.get(key) ?? 0);
    this.values.set(key, val);
    let node = this.root;
    node.sum += delta;
    for (const ch of key) {
      if (!node.children.has(ch)) node.children.set(ch, { sum: 0, children: new Map() });
      node = node.children.get(ch);
      node.sum += delta;
    }
  }

  sum(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      node = node.children.get(ch);
      if (!node) return 0;
    }
    return node.sum;
  }
}

Dry run: insert("apple", 3), sum("ap"), insert("app", 2), sum("ap"), insert("apple", 5), sum("ap")

Insert is O(L), sum is O(P), and memory is O(total characters). The same idea, with 1 instead of a value, gives "how many words start with this prefix" (a prefix count), which also lets you detect that one word is a prefix of another without a flag walk. The brute-force alternative, a map from key to value plus a scan of every key on each sum, costs O(n · L) per query.

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).

Replace Words: stop at the shortest root

A dictionary holds "roots" ("cat", "bat"), and every word in a sentence that starts with a root is replaced by the shortest root that begins it. Build a trie of the roots, then walk each word through it: the first node on the path that is marked as a word end is the shortest root, so return as soon as you meet it. If the walk falls off the trie, or the word ends first, no root applies and the word stays as it is.

function replaceWords(dictionary, sentence) {
  const trie = {};
  for (const root of dictionary) {
    let node = trie;
    for (const ch of root) {
      if (!node[ch]) node[ch] = {};
      node = node[ch];
    }
    node.end = true;
  }

  function shortestRoot(word) {
    let node = trie;
    for (let i = 0; i < word.length; i++) {
      node = node[word[i]];
      if (!node) return word;                  // no root starts this way
      if (node.end) return word.slice(0, i + 1); // first end seen is the shortest root
    }
    return word;
  }

  return sentence.split(" ").map(shortestRoot).join(" ");
}

replaceWords(["cat", "bat", "rat"], "the cattle was rattled by the battery");
// "the cat was rat by the bat"

Building costs O(total root characters). Each word costs at most the length of the longest root, since the walk dies there, so the replacement phase is O(sentence length) rather than O(words · roots). The rejected alternative is to test every root with startsWith for every word. In the code the end marker is stored under the key "end", which cannot collide with a child because child keys are single characters.

Longest Word in Dictionary: every prefix must be a word

Find the longest word that can be built one letter at a time, each prefix also being a word in the list; break ties with the lexicographically smallest. In the trie, a word qualifies exactly when every node on its path is a word end, so search only through children that are word ends. Visiting children in alphabetical order, and replacing the best answer only when a path is strictly longer, makes the first word found at each length the smallest.

function longestWord(words) {
  const root = { end: true, kids: new Map() }; // the empty prefix counts as buildable
  for (const word of words) {
    let node = root;
    for (const ch of word) {
      if (!node.kids.has(ch)) node.kids.set(ch, { end: false, kids: new Map() });
      node = node.kids.get(ch);
    }
    node.end = true;
  }

  let best = "";
  function dfs(node, path) {
    if (path.length > best.length) best = path; // strict: an equal-length later word is lexicographically larger
    for (const ch of [...node.kids.keys()].sort()) {
      const child = node.kids.get(ch);
      if (child.end) dfs(child, path + ch); // a gap in the chain of words ends this branch
    }
  }
  dfs(root, "");
  return best;
}

Dry run: ["w", "wo", "wor", "worl", "world", "banana", "ban", "ba"]

"banana" has the prefixes "ba" and "ban" in the list but no "b", so it cannot be built. The answer is "world". Time O(total characters) for the build plus the walk over the nodes (and the sorts, bounded by the alphabet size at each node). The alternative without a trie sorts the words and keeps a Set of buildable ones: also fine, and worth mentioning.

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.

Deleting a word: unlink on the way back up

Deletion is the operation people skip and interviewers like to ask for. Two separate things might need to happen. The word must stop being a word, which means clearing isEnd on its last node. And nodes that only existed for that word should disappear, otherwise the trie leaks memory and startsWith still answers true for prefixes of a word that is gone. A node is removable when it is not a word end and has no children. The check runs from the deepest node back toward the root and stops at the first node that is still needed.

function removeWord(root, word) {
  const path = []; // [parent, character] pairs from the root down to the last node
  let node = root;
  for (const ch of word) {
    const next = node.children.get(ch);
    if (!next) return false; // the word is not in the trie
    path.push([node, ch]);
    node = next;
  }
  if (!node.isEnd) return false; // the path exists only as a prefix of other words
  node.isEnd = false;

  for (let i = path.length - 1; i >= 0; i--) {
    const [parent, ch] = path[i];
    const child = parent.children.get(ch);
    if (child.isEnd || child.children.size > 0) break; // something else still uses this node
    parent.children.delete(ch);
  }
  return true;
}

Dry run: the trie holds "do" and "dog"

Cost O(L). The two traps are deleting a prefix of another word (removing "do" must keep the nodes d, o, g that "dog" needs) and returning true for a word that was only a prefix. An alternative with the same effect is a counter of words passing through each node, decremented along the path, deleting any node whose count reaches zero.

Stream of Characters: a trie of reversed words

Letters arrive one at a time, and after each one you must say whether some suffix of everything received so far is a dictionary word. A normal trie matches from the start of a word, but here the end is fixed (the newest letter) and the start is unknown. So flip the problem: insert every word reversed, and on each arrival walk the stream backwards from the newest letter. The first word end you reach means a word ends here.

class StreamChecker {
  constructor(words) {
    this.root = { children: new Map(), isEnd: false };
    this.maxLength = 0;
    for (const word of words) {
      let node = this.root;
      for (let i = word.length - 1; i >= 0; i--) { // reversed insert
        if (!node.children.has(word[i])) node.children.set(word[i], { children: new Map(), isEnd: false });
        node = node.children.get(word[i]);
      }
      node.isEnd = true;
      this.maxLength = Math.max(this.maxLength, word.length);
    }
    this.recent = []; // only the last maxLength letters can matter
  }

  query(letter) {
    this.recent.push(letter);
    if (this.recent.length > this.maxLength) this.recent.shift();

    let node = this.root;
    for (let i = this.recent.length - 1; i >= 0; i--) { // newest letter first
      node = node.children.get(this.recent[i]);
      if (!node) return false;   // no word ends with these letters
      if (node.isEnd) return true; // a whole reversed word matched: a suffix of the stream is a word
    }
    return false;
  }
}

Dry run: words ["cd", "f", "kl"], stream a, b, c, d, e, f

Each query costs O(longest word), independent of the stream length, because only the last maxLength letters are kept. The shift() there is also O(maxLength), which does not change the per-query bound. The shape to remember is "match against the end of a growing string, so reverse the dictionary". The general tool for matching many words against a stream is an Aho-Corasick automaton (a trie plus failure links), which does a constant amortized amount of work per letter; the reversed trie is the simpler one to write in an interview.

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
• "Replace with the shortest root," "sum of values by prefix," "count of words with this prefix" → store the answer on the node and read it at the end of the prefix walk
• "Every prefix must also be a word" → only descend through children that are word ends
• Letters arrive in a stream and you ask about a suffix → insert the words reversed and walk backwards from the newest letter
• "Remove a word" → clear the flag, then delete nodes upward while they are not word ends and have no children