Tries

A trie (from retrieval) is a tree where each edge is one character and each root-to-flagged-node path spells a stored word. Words sharing a prefix share a spine, so autocomplete on "py" walks two nodes.

The cost model is unusual: lookup/insert/prefix-search all O(k) where k is query length. Corpus size doesn't appear. Every serious autocomplete, spellchecker, and IP-routing table sits on a trie.

How it works

Each node has a dict from char to child + is_word flag. insert walks the string creating nodes with setdefault, then flips is_word. search walks and checks the flag. starts_with just checks path survival.

__slots__ cuts memory noticeably at million-node scale. For alphabet-only, swap dict for fixed-size list indexed by ord(ch) - ord('a').

Common bugs

• Forgetting is_word. "car" present incorrectly reports "ca" as stored.
• Overwriting nodes. Use setdefault.
• Delete is not just clearing the flag. Prune leaves up while stopping at surviving branches. Most interview answers just clear the flag.
• Case + unicode. Normalize on insert.

Try it

1. Add count_words_with_prefix(prefix) returning count. Track counter on each node updated during insert.
2. Extend the walk to support ? wildcard matching any single character.