Words as Paths

A trie (prefix tree) answers questions no hash map can: not "is this string present?" but "does anything present starts like this?" It stores each word as a path from the root — one character per edge — so all words sharing a prefix share the path to it. Insertion is a walk that creates missing edges; search is a walk that must not fall off.

A path is not a promise

The single most important fact in a trie: arriving somewhere is not matching. The path for admin exists inside the path for administrator, and only one of them is a word. The difference is one flag on the final node:

interface TrieNode {
  children: Map<string, TrieNode>
  isEndOfWord: boolean
}

export class Trie {
  #root: TrieNode = { children: new Map(), isEndOfWord: false }

  insert(word: string): void {
    let node = this.#root
    for (const ch of word) {
      let next = node.children.get(ch)
      if (next === undefined) {
        next = { children: new Map(), isEndOfWord: false }
        node.children.set(ch, next)
      }
      node = next
    }
    node.isEndOfWord = true
  }

  search(word: string): boolean {
    let node: TrieNode | undefined = this.#root
    for (const ch of word) {
      node = node.children.get(ch)
      if (node === undefined) return false
    }
    return node.isEndOfWord
  }
}

Insert never looks ahead — it walks, creating nodes as needed, and marks where it landed. Search walks without creating and then asks the node it landed on the only question that matters: did a word end here? Returning "the walk survived" instead of the flag is the classic trie bug, and it fails in the worst direction — prefixes of real words count as real words, so a blocklist built on it flags identifiers nobody banned.

function insert(word: string): void {
  let node = root
  for (const ch of word) {
    let next = node.children.get(ch)
    if (next === undefined) {
      next = { children: new Map(), isEndOfWord: false }
      node.children.set(ch, next)
    }
    node = next
  }
  node. = true
}

Autocomplete is a walk plus a collect

Every completion of a prefix lives in the subtree under the prefix's final node. So: walk the prefix (dead end → no completions, return empty), then collect every word-end beneath, walking children in sorted key order — which yields dictionary order for free, no final sort.

const collect = (current: TrieNode, walked: string): void => {
  if (current.isEndOfWord) results.push(walked)
  for (const ch of [...current.children.keys()].sort()) {
    collect(current.children.get(ch) as TrieNode, walked + ch)
  }
}

The recursion's shape is worth noticing: it is the subsets skeleton from the backtracking chapter wearing different clothes — a DFS over an implicit tree, collecting at nodes instead of leaves. Patterns compose like that constantly, and recognizing "this is that, with a different collect condition" is most of interview fluency.

Wildcards: the fan-out move

A . in a query matches any single character. On a literal trie walk there is no "any" edge to follow — so follow all of them:

function match(node: TrieNode, rest: string): boolean {
  if (rest.length === 0) return node.isEndOfWord
  const ch = rest[0] as string
  const tail = rest.slice(1)

  if (ch !== '.') {
    const next = node.children.get(ch)
    return next !== undefined && match(next, tail)
  }
  for (const next of node.children.values()) {
    if (match(next, tail)) return true
  }
  return false
}

The wildcard branch turns one walk into many, each an independent search of the remaining query — and the trie is what keeps the fan-out affordable: sharing prefixes means the fan-out only happens where the words genuinely diverge. Each dot must consume exactly one character (t.m does not match team), which falls out of passing tail to every branch: the recursion's depth is the query's length, character for character.

if (ch !== '.') {
  const next = node.children.get(ch)
  return next !== undefined && match(next, tail)
}
for (const next of node..values()) {
  if (match(next, tail)) return true
}

How to debug a trie

Print it as the paths it secretly is — every word-end and the path that reaches it. A trie "with a search bug" printed this way usually reveals the insert never set the flag: paths exist, no ends. For autocomplete order, print the children keys at each level in iteration order; a Map iterates in insertion order, not sorted — if you collect without sorting the keys, completions come out in the order words were inserted, which looks correct on a dictionary inserted alphabetically and is wrong on any real input. For wildcards, log each fan-out with the remaining query; a dot consuming two characters shows up immediately as a tail that skipped.

Where this bites

• Search trusting arrival. The walk surviving proves the characters continue, not that a word ends — every prefix becomes a hit. Counter: the return statement is the flag, always; the walk's job is only to deliver you to the node that owns it.
• Collecting completions in insertion order. Map iteration order is insertion order; results order correctly only for alphabetically-inserted dictionaries and silently misorders real ones. Counter: sort the child keys as you descend — the DFS then emits dictionary order with no final sort.
• Insert marking every node on the path. Setting the flag inside the loop marks each prefix as a word; car starts matching when only cardigan was inserted. Counter: the flag is set exactly once, after the loop, on the final node — the walk's last step.
• A dot that matches a run of characters. Passing rest instead of tail to the recursive branch lets one dot eat eam — matches multiply. Counter: the query shrinks by exactly one character per level, on every branch, literal or wildcard.