Tries

A trie (from “retrieval”; sometimes called a prefix tree) stores words as paths of characters. The root is the empty prefix; inserting "bat", "ball", and "bath" stores the shared prefix "ba" only once:

            ⌀
           /  \
          b    c
         /      \
        a        a
       / \       / \
      t*  l     p*  t*
     /    |         |
    h*    l*        r? → cap, cat, car

* marks an end-of-word flag — it distinguishes a complete word from a mere prefix (like "ba").

The Three Core Operations — All O(m)

OperationCostWhy
insert(word)O(m)walk m characters, create missing nodes
search(word)O(m)walk edges; success only if end-of-word is set
startsWith(prefix)O(m)walk the prefix, then enumerate its subtree

Crucially, none of these depend on how many words are stored — a lookup never scans the whole dictionary. That is the trie’s superpower over hashing-based solutions.

Memory Trade-off

A naive trie with a 26-letter alphabet can spend ~26 pointers per node, making space O(Σ · n · m) in the worst case. Compressions exist:

  • Compressed trie / Patricia trie — merge single-child runs into one edge.
  • Ternary search trie — each node stores one char + three children (lower, equal, higher), halving memory at a small speed cost.
  • Radix tree (used in Linux routing and Redis) — edges labeled with strings.

When to Reach for It

  • Autocomplete — startsWith plus subtree enumeration gives all suggestions.
  • Spell checking — word membership plus prefix matching for “did you mean?”.
  • Longest-prefix match — the IP routing table lookup in every router.
  • Sorting words — DFS over the trie yields sorted output in O(total chars).

Use a hash set when you only need membership; use a trie when you also need prefix queries, ordering, or longest-prefix matching.

Practice Trajectory

  1. Implement insert/search/startsWith with arrays-of-26 for the alphabet.
  2. Add a delete that cleans up nodes with no other word beneath them.
  3. Implement autocomplete returning the k most likely completions.
  4. Build a compressed trie and compare node counts on real word lists.
  5. Solve: word search, longest-word-with-all-prefixes, and IP-longest-prefix problems.