Trie (Prefix Tree)

How to read this

• Each circle is a node; the letter on it is the edge you followed to get there. Reading the letters from the root down spells a prefix.
• A green ring means isEnd = true: a stored word ends here. Without that flag, "ca" would look like a word just because "car" passes through it.
• The small number under a node is pass: how many stored words go through it. It turns "how many words start with p?" into one walk of |p| steps, and it tells delete which nodes nobody else uses.
• The two bars at the bottom compare the total characters of all stored words with the number of letter nodes. The gap is what prefix sharing saves.
• Counters: steps counts child lookups in this operation, which is at most the length of the word, independent of how many words are stored.

Try this

1. Build the default list car, card, care, cat, dog, dot. You should get 11 nodes (10 letters + the root) for 20 characters, so sharing saves 10 letter nodes.
2. Search ca: every letter is found, yet the answer is false because the node for "a" has no green ring. Then run prefix count on ca: 4 words (car, card, care, cat).
3. Search cow: the walk stops at the dashed "o" under "c" after 2 steps. A miss can be even cheaper than a hit.
4. Delete card: only the "d" node disappears. Then delete car: no node disappears, only the green ring on "r" (because "care" still uses it).
5. Add words with no shared beginnings (zebra, quilt, juice). Watch the node count approach the character count: a trie saves space only when prefixes are shared.

Go deeper