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)

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.

Compressed (Patricia) Tries

A plain trie spends a node on every character, even when a chain has no branches. A compressed trie (Patricia — Practical Algorithm To Retrieve Information Coded In Alphanumeric) merges any single-child run into one edge labeled with the whole string:

plain:      b → a → t *  → h *        (4 nodes for "bat"+"bath")
                                   │
compressed: "ba" → "t"* → "h"*      (3 nodes; shared prefix still one path)

The savings are dramatic on real dictionaries: node count drops from O(total characters) to O(number of words × depth-of-common-prefix), which is why Patricia tries power IP longest-prefix routing tables, Redis key dictionaries, and Git’s object storage. The trade-off is that deleting a word can require re-merging edges, and each edge carries a string instead of a single char. The lookup cost is still O(m) in the number of characters — the structure just spends far fewer nodes per word.

Ternary Search Tries (TST)

A TST is the midpoint between a trie and a BST: each node holds one character and three pointers — lo (chars < current), eq (continuation of the word), hi (chars > current). It uses O(3) pointers per character instead of O(26), slashing memory for large alphabets (Unicode!), at a lookup cost of O(m + log N) (N = number of stored keys) instead of O(m). Java’s TreeMap-like string keys and several symbol-table libraries use TSTs precisely because they get trie-style prefix operations with BST-style space.

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).
• XOR maximization — insert the numbers into a binary trie (bits 31→0 as edges), then for a query x greedily walk the opposite bit at each level; each step doubles the value’s leading bits, so the best XOR pair in an array is found in O(32) per number. This is the standard O(n log max) solution to the classic “maximum XOR of two numbers in an array” interview problem — a hash map can’t do prefix searches, but a trie can.

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

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.
6. Implement a binary XOR trie and solve “maximum XOR of two numbers in an array.”