Tries: One Node per Letter

A trie is a tree that stores words letter by letter, so that every word is a path from the root and words with the same beginning share the same nodes. This card covers how a trie is laid out, the end-of-word mark that tells a stored word from a mere beginning of one, and what its operations cost. Its strength is the prefix, the opening letters of a word: a trie answers whether any stored word starts with a given prefix without looking at the words that do not.

The root holds no letter. Each node has at most one child for each possible next letter, and a node carries an end-of-word mark when the path from the root to it spells a stored word. The name comes from retrieval and is usually said like "try".

The tree below holds the words sun, sum, sung and sky. All four start with s, so they share one s node; sun, sum and sung share s and u as well. Seven nodes below the root hold the 13 letters of the four words, as a run that built this trie counted.

The n node shows why the mark is needed. It ends the word sun and also sits in the middle of sung, so the path alone cannot say whether sun was stored. The u node has no mark, because su was never inserted, even though a path for it exists.

A phone's contacts list behaves much like a trie: each letter typed narrows the list to the names that start with the letters typed, and the number of contacts makes no difference to how one letter narrows it. The likeness breaks at where the match may start. A phone often matches letters anywhere in a name, such as a surname, while a trie matches only from the first letter, because every path begins at the root.

Every operation walks down from the root one letter at a time, so its cost depends on L, the length of the word or prefix, and not on how many words the trie holds.