Trie (Prefix Tree)

A trie, also known as a prefix tree, is a tree-like data structure used to store and efficiently retrieve strings. Each node represents a character, and paths from the root represent prefixes. Tries are particularly useful for tasks like auto-completion, spell checking, and IP routing due to their ability to quickly identify strings sharing common prefixes.