a trie

Think of an old-fashioned card catalog organized by spelling: all words starting with 'c' live behind the 'c' tab, then 'ca' behind a sub-tab, then 'cat', 'car', 'cab' fanning out further. A trie is exactly this idea as a tree. Each edge is labeled with one character, and the path from the root down to a node spells out a prefix. Words that share a beginning share the upper part of their path, so the structure naturally groups by common prefix.

Concretely, a trie is a rooted tree where each node has at most one child per alphabet symbol. To insert a word, you walk down from the root following its characters, creating any missing nodes, and mark the final node as the end of a word. To look up a word you walk the same path; reaching a node marked 'end of word' means it is present. Searching or inserting a word of length L costs O(L) regardless of how many words the trie holds — the cost depends on the word, not the dictionary size, which is a key advantage over a balanced binary search tree where each comparison itself scans a whole string. Tries also make prefix queries trivial: to find all words starting with "car", walk to the "car" node and collect everything in its subtree. The plain trie can waste memory when many nodes have a single child; a compressed trie (also called a radix or Patricia tree) merges each such chain into one edge labeled with a whole substring, shrinking the structure while preserving its behavior.

Tries are everywhere prefixes matter: autocomplete and predictive text, IP routing tables (longest-prefix match), spell-checkers, and as the backbone of Aho-Corasick multi-pattern matching. The honest trade-off is space: a naive trie over a large alphabet can use a child-pointer slot per symbol per node, which is wasteful for sparse data — hence the compressed and array-versus-hashmap variants. But for prefix-centric workloads the trie's O(length) operations and effortless prefix enumeration are hard to beat.