Trie

overview

Summary

A trie is a prefix tree for strings that stores characters along paths, sharing common prefixes across keys. It offers O(L) insert, search, and prefix queries where L is the key length, largely independent of the number of stored keys. Tries trade memory for fast, predictable lookups and rich prefix operations like autocomplete and lexicographic listing. They are foundational in search systems, dictionaries, and routing with longest prefix match.