Tries

A user types ca into a search box. You need every word that starts with it, right now, out of a dictionary of 300,000.

The obvious way

const matches = words.filter((w) => w.startsWith('ca'));

300,000 comparisons per keystroke. And a hash map does not help: hashing destroys the relationship between cat and cart by design — a good hash sends similar keys to completely different buckets.

Prefix questions need a structure where similar keys are stored near each other.

The realisation

Do not store the words. Store the letters, once each, in a tree.

Every node is one character. Following a path from the root spells a prefix, and the words sharing that prefix are exactly the nodes below it.

Walk the query cart one letter at a time:

Notice car and cart and cat share their c and a. That sharing is the whole idea: the structure stores each distinct prefix once, no matter how many words use it.

The structure

class TrieNode {
  children = new Map<string, TrieNode>();
  isWord = false;         // ← does a word *end* here?
}

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.isWord = true;
  }

  /** Walk the prefix; null if it runs out of tree. */
  private walk(prefix: string): TrieNode | null {
    let node = this.root;
    for (const ch of prefix) {
      const next = node.children.get(ch);
      if (!next) return null;
      node = next;
    }
    return node;
  }

  has(word: string): boolean { return this.walk(word)?.isWord ?? false; }
  hasPrefix(prefix: string): boolean { return this.walk(prefix) !== null; }
}

Two things are worth staring at.

No node stores a string. The prefix is the path, not data. cart exists nowhere in memory as a string — it is four nodes, and reading it back means walking down.

isWord is not optional. Without it, walk('do') succeeds because do is on the way to dog, and you cannot tell a stored word from a passing prefix. That is why has and hasPrefix are two different methods, and mixing them up is the classic trie bug.

The costs

Note the first row: a hash map is not actually faster for exact lookup. It still has to read the whole key to hash it. The trie’s real disadvantage is elsewhere.

What it is genuinely the right answer for

Autocomplete. Walk to the prefix node, then depth-first from there to collect the words below. Store a “most popular completion” on each node and you can serve the top suggestion in $O(L)$ without collecting anything.

Spell check with edit distance. Walk the trie and the dynamic programming row together, abandoning any branch whose best possible distance already exceeds the budget. The prefix sharing means one prune skips thousands of candidate words.

Search many needles in one haystack. The Aho–Corasick algorithm is a trie of all the patterns plus “failure links” that say where to jump on a mismatch. grep -f patterns.txt is this, and it scans the text once regardless of how many patterns you gave it.

IP routing. Longest-prefix match is exactly the walk-until-you-fall-off operation, on a binary trie over address bits.

If your only question is “is this exact thing in the set?”, use a hash map. The trie earns its memory when the question is about prefixes.