Trie (Prefix Tree)

A tree of letters that makes “does any word start with this?” very fast.

The idea (phone auto-complete)

When you type “ca” and your phone suggests “cat”, “car” and “cart”, something has to find every word that starts with “ca” without scanning the whole dictionary. A trie stores words as paths of letters from a single root. Words that start the same way share the same beginning of the path.

Notice: car is a prefix of cart. Both can be words, so “word end” is a separate mark, not the same as “has no children”.

Watch it work

Try it

Common mistakes

Complexity, in plain English: insert, search and prefix checks all cost one step per letter of the word, no matter how many words are stored (O(L) for a word of length L). The price is memory: up to one node per stored letter.