Trie: A Prefix Tree

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

Words: cat, car, cart, dog        (* marks a node where a word ends)

              (root)
             /      \
            c        d
            |        |
            a        o
           / \       |
          t*  r*     g*
              |
              t*

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