A tree shaped by shared prefixes
A trie, also called a prefix tree, stores a set of strings so that common prefixes are shared. Each edge is labelled with a character, and the path from the root to a node spells out a prefix. Nodes that complete a stored word are marked as terminal.
Why prefixes get cheaper
Because words that begin alike share the same early path, looking something up depends on the length of the query, not on how many words are stored. Walking from the root following each character either reaches the right node or falls off the tree, meaning no match.
What it is good for
- Autocomplete: once you reach the node for a typed prefix, every word beneath it is a completion.
- Dictionary membership: check whether a word ends at a terminal node.
- Prefix counting: store a count at each node to answer how many words share a prefix.
The cost is memory, since every distinct character at every level needs a child slot or map entry. Compressed variants merge single child chains to reclaim space while preserving the same lookups.
Key idea
A trie stores strings along character labelled paths so shared prefixes are stored once; lookups depend only on query length, making prefix membership, counting, and autocomplete fast at the cost of extra memory.