Trie

A trie (prefix tree) stores words letter by letter down a tree, so words that start the same way share the same path — perfect for autocomplete.

An empty trie

•
  • Path being followed
  • End of a word
  • Autocomplete subtree

A trie stores words letter by letter down a tree. Words that share a beginning share the same path.

Step 1 / 36
Letter nodes
0
Words
0

Step by step

The example above, written out — the same steps the animation plays.

  1. 1An empty trie. A trie stores words letter by letter down a tree. Words that share a beginning share the same path.
  2. 2Insert "car": letter "c". No "c" here yet — create it.
  3. 3Created "c". New node for "c".
  4. 4Insert "car": letter "a". No "a" here yet — create it.
  5. 5Created "a". New node for "ca".
  6. 6Insert "car": letter "r". No "r" here yet — create it.
  7. 7Created "r". New node for "car".
  8. 8"car" stored. Mark the last letter as the end of a word (the ring).
  9. 9Insert "cart": letter "c". "c" already exists here — follow it (shared prefix "c").
  10. 10Insert "cart": letter "a". "a" already exists here — follow it (shared prefix "ca").
  11. 11Insert "cart": letter "r". "r" already exists here — follow it (shared prefix "car").
  12. 12Insert "cart": letter "t". No "t" here yet — create it.
  13. 13Created "t". New node for "cart".
  14. 14"cart" stored. Mark the last letter as the end of a word (the ring).

…and 22 more steps — press Play above to watch them all.

What's happening?

  1. Inserting a word follows existing letters and creates new nodes only where the word differs.
  2. The node for a word's last letter is marked as the end of a word.
  3. To autocomplete, follow the prefix, then collect every word in the subtree below it.

Complexity

Time
O(L) to insert or look up a word of length L — however many words are stored
Space
Up to one node per letter stored

Where you'll meet it

Search-box autocomplete, spell checkers, IP routing tables (longest-prefix match), and word games.

Common mistake

Forgetting the end-of-word mark: without it, storing "cart" would make "car" look like a word too.

FAQ

Why is lookup independent of how many words there are?

You only ever walk down as many levels as the word has letters.

Trie vs hash map?

A hash map answers "is this exact word here?" just as fast, but cannot list every word with a given prefix.

Don't tries use a lot of memory?

They can. Compressed tries (radix trees) merge chains of single children to save space.