Trie

A tree of letters.

A trie (pronounced "try," from retrieval) stores words letter by letter as a tree. Words that share a beginning share the same path — so "car," "cart," and "care" all start down the same branch. It's ideal for autocomplete and spell-checking.

• Each node represents one character; a path from the root spells a prefix.
• A flag marks nodes that complete a word (end-of-word).
• Great for "does any word start with this prefix?" questions.

Complexity and cost.

Insert, search, and prefix lookup take O(L) where L is the word length — independent of how many words are stored, which beats a hash set for prefix queries.

• Prefix search — walk L nodes to a prefix, then collect the subtree for autocomplete.
• Memory cost — a child map/array per node can be large (e.g. 26 pointers per node for lowercase English), the trie's main downside.

Compression and specializations.

• Radix / Patricia trie — merges single-child chains into one edge, cutting memory drastically for sparse key sets (used in IP routing tables).
• Ternary search trie — stores children as a small BST per node, saving space over a full array while staying fast.
• Aho–Corasick — a trie with failure links for multi-pattern string matching in one pass.
• Uses — autocomplete, spell-check, dictionary/IME, longest-prefix-match routing, and word games.