Module A-10·13 min read

Prefix trees for O(L) lookups — autocomplete, wildcard search, and why a trie beats a hash map for prefix queries.

Written by Jatin Jain Saraf · Architect of SupraScan

Module A-10 — Tries: Prefix Trees and Autocomplete

What this module covers: Module F-4's hash map answers "does this exact key exist" in O(1). It has no good answer at all for "what keys start with this prefix" — that requires scanning every key. A trie is a tree built specifically to make prefix queries fast, by encoding shared prefixes as shared paths through the tree. This module covers the structure, its core operations, and autocomplete — the application a trie is built for.

The Structure: Shared Prefixes Are Shared Paths

A trie (from retrieval, though commonly pronounced "try" to avoid confusion with "tree") is a tree where each edge represents one character, and any path from the root spells out a prefix. Words that share a prefix — "car", "card", "care" — literally share the same path through the tree for their common letters, only branching apart where they first differ.

class TrieNode {
  children: Map<string, TrieNode> = new Map(); // char -> next node (Module F-4)
  isEndOfWord: boolean = false;                 // marks "a complete word ends exactly here"
}
 
class Trie {
  private root = new TrieNode();
 
  insert(word: string): void {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char)!;
    }
    node.isEndOfWord = true; // mark the END of this specific word, not every node visited
  }
}

"car", "card", and "care" inserted into the same trie produce a single shared path for c → a → r, with the tree only branching into three separate continuations (nothing further, d, or e) at that point — the shared prefix is stored exactly once, no matter how many words share it. isEndOfWord matters specifically because a word can be a prefix of another word ("car" is a prefix of "card") — without this flag, there'd be no way to tell whether the path to a given node represents a complete, insertable word or just an intermediate letter on the way to a longer one.

Search and StartsWith: Both Just a Walk Down the Tree

class Trie {
  // ...(insert above)
 
  search(word: string): boolean {
    const node = this.walk(word);
    return node !== null && node.isEndOfWord; // must exist AND be a complete word, not just a prefix
  }
 
  startsWith(prefix: string): boolean {
    return this.walk(prefix) !== null; // just needs to exist as a path — doesn't need isEndOfWord
  }
 
  private walk(str: string): TrieNode | null {
    let node = this.root;
    for (const char of str) {
      if (!node.children.has(char)) return null; // this path doesn't exist in the trie at all
      node = node.children.get(char)!;
    }
    return node;
  }
}

Both operations are the identical walk, differing only in the final check: search additionally requires isEndOfWord (this exact string was inserted as a complete word), while startsWith only cares that the path exists at all (some word in the trie begins this way). Both cost O(L), where L is the length of the string being searched — critically, independent of how many words the trie holds. This is the trie's core advantage over a hash map (Module F-4): a hash map's O(1) lookup only answers "does this exact key exist" — it has no efficient way at all to answer "what keys start with this prefix," short of checking every single key it holds, which is O(n × L) in the worst case. A trie answers the prefix question in the same O(L) it takes to answer the exact-match question, because the tree structure itself is organized by shared prefixes.

Autocomplete: Walk to the Prefix, Then Collect Everything Below It

Autocomplete needs "every word starting with this prefix," not just "does this prefix exist." The fix: walk to the prefix's node (exactly startsWith's walk), then run a traversal (Module P-4) from that point, collecting every complete word found in the subtree beneath it.

function autocomplete(trie: Trie, prefix: string): string[] {
  const prefixNode = (trie as any).walk(prefix); // conceptually: reuse the same walk from startsWith
  if (prefixNode === null) return [];
 
  const results: string[] = [];
 
  function collectWords(node: TrieNode, currentWord: string): void {
    if (node.isEndOfWord) results.push(currentWord);
 
    for (const [char, child] of node.children) {
      collectWords(child, currentWord + char); // Module P-4's preorder shape: visit, then recurse into children
    }
  }
 
  collectWords(prefixNode, prefix);
  return results;
}
 
// trie contains: "car", "card", "care", "cart", "dog"
autocomplete(trie, "car"); // ["car", "card", "care", "cart"]

function searchWithWildcard(root: TrieNode, word: string): boolean {
  function dfs(node: TrieNode, index: number): boolean {
    if (index === word.length) return node.isEndOfWord;
 
    const char = word[index];
    if (char === '.') {
      for (const child of node.children.values()) {
        if (dfs(child, index + 1)) return true; // try every possible branch — Module P-7's backtracking shape
      }
      return false;
    }
 
    if (!node.children.has(char)) return false;
    return dfs(node.children.get(char)!, index + 1);
  }
 
  return dfs(root, 0);
}