Recap: Tries

Shared prefixes share a path, a mark ends each word, and prefix search ignores the word count.

Tries come down to the five ideas below, each listed with the card that covers it. One fact explains all of them: every word is a path from the root, one node per letter, so any question about a word or a prefix is a walk whose length is the number of letters asked about.

What the topic established, and which card it was on
The idea	Where
The root holds no letter, words with the same beginning share nodes, and each operation costs O(L) for L letters	Tries: One Node per Letter
Insert follows existing children and creates missing ones, then marks the last node; search stops at the first missing child	Insert and Search a Word in a Trie
Without an end-of-word mark, every prefix of a stored word is reported as a stored word	A Trie Without an End-of-Word Mark
No standard library has a trie; a map of children per node accepts any character, an array of 26 suits lowercase letters only	Trie in Python, Java and TypeScript
A hash set matches a trie on exact words and uses less memory; only the trie answers a prefix question without checking every word	Trie vs Hash Set of Words

The picture to keep is a small trie with both kinds of node in it: n ends sun and also leads on to sung, while u is on the path of three words and ends none.

The trie holding sun, sum, sung and sky

root
- s
  - u, no mark: su is not a word
    - n, end of word: sun
      - g, end of word: sung
    - m, end of word: sum
  - k
    - y, end of word: sky

Together they let you build a trie by hand, search it for a word or a prefix, list the words under a prefix, write one in any of the three languages, and decide when a hash set is the better choice.

← → move through sections and cards