Tries

A trie, also called a prefix tree, is a tree for storing words where each step down the tree spells one more letter. Words that start the same way share the same path from the top: “car”, “cart” and “care” all go through c, a, r before branching. Looking up a word takes as many steps as the word has letters, no matter how many words are stored, and finding every word with a given prefix is just walking to that prefix and listing everything beneath it. That makes tries a natural fit for autocomplete, spell checkers and IP routing tables. A radix tree saves memory by merging chains of single-child nodes into one edge.