A tree of prefixes
A trie, also called a prefix tree, stores a set of strings as a tree where each edge is labeled with a character. A key is not stored in one node; instead it is spelled out by the path of edges from the root. Strings that share a prefix share the same initial path.
How lookups work
To search for a word you start at the root and follow one edge per character. If at any step the needed edge is missing, the word is not present. If you consume the whole word, you check a flag on the final node marking it as a complete key, since a path can pass through without ending there.
Because you walk one node per character, a lookup depends only on the length of the key, not on how many strings the trie holds.
What it is good at
The shared structure makes tries excellent for prefix queries:
- Autocomplete, gathering every word under a prefix node.
- Longest prefix matching, used in routing and dictionaries.
The cost is memory, since each node may fan out to many children.
Key idea
A trie spells keys along character labeled edges so shared prefixes share paths, making lookups depend only on key length and excelling at autocomplete and prefix matching.