Trie: A Prefix Tree

A trie stores strings sharing common prefixes by sharing tree nodes.

Words: cat, car, cart, dog

         (root)
        /      \
       c        d
       |        |
       a        o
      / \       |
     t   r      g
     *   |   (* = end of word)
         (also a path to cart...)

Each path from root to a marked node is a word. Common prefixes share branches (cat and car both go through c->a).

Compared to a hash set:

• Hash set: O(1) lookup; can't enumerate prefixes.
• Trie: O(m) lookup (m = word length); easy prefix queries.

Tries are fast for "all words starting with pre" — walk down to pre (m steps), then DFS the subtree.

Used in:

• Autocomplete (search bars, IDEs)
• Spell checkers (with edit-distance walks)
• IP routing tables (longest-prefix match)
• Dictionary structures