Tries: one letter per edge

Type “ca” on a phone and it offers car, card and cat before you reach the third letter, from a dictionary of a few hundred thousand words. A hash set of those words would say at once whether “cat” is one of them, but to find the words that start with “ca” it would have to check every word it holds.

A trie (usually said “try”; the name comes from retrieval) is built for that question. It stores words letter by letter along paths down from a root, so every word that starts with “ca” sits below one node. Reaching that node takes two steps, one per letter, however many words the trie holds.

trie (prefix tree)

A tree whose edges are letters. The path from the root down to a node spells that node's prefix; the root stands for the empty string.

prefix

The first few letters of a word: “ca” is a prefix of “car” and of “cat”. A word counts as a prefix of itself.

end-of-word mark

A flag on a node saying that a stored word ends there, drawn as a double ring. Without it, a trie can't tell a stored word from the start of a longer one.

children

How a node reaches the next letter: a map from each letter to its child node, or an array of 26 slots, one per letter, most of them empty.

search and starts-with

Search asks whether a whole word is stored. Starts-with asks whether any stored word begins with a prefix; autocomplete goes on to list them all.

This trie holds car, card, care, cat, do, dog and dot. Its nodes carry no letters themselves: each edge is labelled with one, and the path down to a node spells its prefix. The four words starting with c hang below one node for “c” and one for “ca”, so those two letters are stored once, not four times.

Insert follows the child for each letter where there is one and adds one where there isn't (after the first added node, every letter needs a new one), then marks the node it stopped on. Search walks the same way and gives up at the first missing child. Autocomplete walks to the prefix's node and collects everything below it: each node's own word first, then its children from a to z, so the words come out in alphabetical order.

Insert and search never look at a word off their path. Each step asks one node for one child, so a word of length L takes at most L steps, whether the trie holds seven words or seven million. A balanced binary search tree of n words does worse: it compares the target with about log₂ n stored words, and each comparison can read up to L letters, so a search costs O(L log n).

Before each answer, look at where the walk stops: is that node marked, and does anything hang below it? Search for “ca”, then for “cat”. Run Autocomplete with “do”. Then delete “card”, and after it “car”. Each of those five operations asks one question.

Here is a trie in code. Each node is a map (a dict in Python, an object in JavaScript) from a letter to its child, and the key '$' marks the end of a word. insert walks down the word, makes any missing child, marks the last node and returns how many nodes it added. search walks the same way and answers yes only if the node it stops on is marked. The program inserts “car” and “cat”, prints how many nodes the trie has, root included, and then asks whether “ca” is stored.

def insert(node, word):
    added = 0
    for ch in word:
        if ch not in node:
            node[ch] = {}
            added += 1
        node = node[ch]
    node['$'] = 1
    return added

def search(node, word):
    for ch in word:
        if ch not in node:
            return 'no'
        node = node[ch]
    if '$' in node:
        return 'yes'
    return 'no'

root = {}
nodes = 1
nodes += insert(root, 'car')
nodes += insert(root, 'cat')
print(nodes)
print(search(root, 'ca'))

The search for “ca” met no missing child and still said no. Without that last check, a trie reports every prefix of every word as a word.

For whole words, a hash set does as well: both answer “is cat stored?” in O(L) on average, since hashing reads all L letters. The trie wins on prefixes. Starts-with is a walk of p steps for a prefix of length p, and autocomplete visits only the nodes below it, where a hash set would check every word. Collecting from the root lists every word in sorted order, where a hash table would have to sort its keys first.

So tries turn up wherever keys are matched by how they start: search boxes that complete what you type, spell checkers that walk the trie letting a letter differ, word-game solvers that abandon a path of letters once no word starts with it, and routers that walk a trie of address bits to find the longest stored prefix of a packet's address.

Delete has to undo an insert without harming the other words that share its path.

A trie's price is memory: a node for every distinct prefix, each carrying its children. Sharing helps only where words start the same way: “internal” and “interval” share five nodes, then need three each.

• A trie stores words along paths from the root, one letter per edge, so words that share a prefix share its nodes.
• Insert, search and starts-with follow at most L children for a word or prefix of length L: O(L), however many words are stored.
• A search must end on a marked node: “ca” is not stored just because “car” is.
• Autocomplete walks to the prefix's node and collects everything below it, in sorted order when children are visited from a to z. A hash set would check every word.
• Delete clears the mark, then removes nodes on the way up only while no other word needs them.
• The price is memory: a node for every distinct prefix, each with a child map or an array of slots.
• Next: string matching, which finds a pattern anywhere inside a text. Practise with Build a Prefix Tree, then Word Dictionary with Wildcards, where a . matches any letter, so the search tries every child and backs up when a branch fails, as in backtracking. Or open the trie visualiser to try more operations.