Trie

A trie (prefix tree) stores strings character by character, enabling O(L) insert, search, and prefix queries where L is string length. Use it for autocomplete, word search in a grid, longest common prefix, and IP routing. Each node has up to 26 children (for lowercase letters).