Tries (Prefix Trees)

A trie (prefix tree) stores words so you can look them up letter by letter: a path from the root down to a marked node spells a word, and words that share a beginning share the same path near the top.

Node shape

• children: dictionary mapping each next character to its child node.
• is_end: true/false flag meaning “a word ends exactly here.” Needed because a word can be a prefix of a longer word (car inside card).
• The root holds no character; it is just the entry point.

Operations

• insert(word): walk from root; for each char, create the child if missing, then step into it. After the last char, set is_end = True.
• search(word): walk the chars. If any link is missing, not found. At the end, return the is_end flag (reaching a node is not enough).
• startswith(prefix): same walk, but only check the path exists; ignore the flag.

       root
      /    \
   c        d
   |        |
   a        o
  / \       |
 t*  r*     g*     * = is_end
      |
      d*        cat, car, card, dog

Insert reuse

• Adding card to a trie with cat, car, dog reuses c -> a -> r; only the new d node is created.
• r keeps its end mark: car and card both live on one path (car ends at r, card at d). The flag makes this possible.

Big-O

L = length of word/prefix, A = alphabet size. Dict lookup/insert is O(1) average, so one step per character.

• Cost does not depend on how many words are stored, only on L. That is the headline advantage.
• Total trie space is O(total chars) worst case; shared prefixes are stored once.

Uses

• Autocomplete / type-ahead (walk to prefix node, explore below).
• Prefix matching and validation, spell checkers, word games.
• IP routing and phone-number prefixes (works on digits/bits too).

Gotchas

• Forgetting is_end: cannot tell a stored word from a mere prefix; search("ca") would wrongly return true.
• Confusing search and startswith: they walk identically but decide differently (flag vs. path exists). Most common trie bug.
• Each missing link must get a fresh TrieNode(); sharing one node corrupts branches.
• Empty string "" sets is_end = True on the root itself; legal but easy to miss.
• Case matters: Car != car. Lowercase before insert/search for case-insensitive matching.