Lesson 22 — Trie (expert)

Trie: a tree of prefixes

A trie (say "try") stores words letter by letter in nested dicts: shared prefixes share the same path. "car" and "cat" share c → a, then split. A special key "#" marks where a full word ends. Searching walks one letter at a time; if a letter is missing, the word is not there.

root = {"c": {"a": {"r": {"#": True}, "t": {"#": True}}}}

Why it matters: autocomplete and spell-checkers use tries because "all words starting with ca" is just one walk down the tree.