Prefix trees

A trie stores words by their letters. Words that start the same way share the same first nodes. This makes one question very fast that a hash set cannot answer well: does any stored word start with these letters?

Words that share a start

A prefix of a word is its first few letters. te is a prefix of tea and of ten. The whole word counts as a prefix of itself, and so does the empty string.

Many programs need to answer two questions about a large set of words:

• Is this exact word stored? (A spell checker.)
• Does any stored word start with this prefix, and which ones? (A search box that suggests words as you type.)

A Python set answers the first question quickly, but not the second: to find words that start with te it must look at every word. A sorted list with binary search (BSRC) can answer both, but each step of the search compares whole strings. A trie answers both by reading the prefix one letter at a time, and it never looks at words that do not match. The name comes from retrieval. Most people say it like “try”.

The shape of a trie

A trie is a tree. Each edge (the line from a node down to a child) carries one letter, and the letters on the edges below a node are all different. Reading the letters on the path from the root down to a node spells a prefix, and we say the node stands for that prefix. The root stands for the empty prefix.

Some prefixes are whole words and some are not. So each node also has a mark that says “a stored word ends here”. In the figures this mark is a small black end tag. Step through the figure to see five words go in.

Why exactly one? Two different paths from the root must split at some node, and after the split they take edges with different letters. So they spell different prefixes. In the other direction, every prefix of a stored word was walked or created when the word was inserted.

Notice the last two words in the figure. inn was inserted first and created the nodes i, in and inn. When in came next, its node was already there, so the insert only added the end tag. Without the tag, the trie could not tell the word in from a prefix that happens to be on the way to inn.

A node in Python

The simplest node keeps its children in a dict, from a letter to the child node, and one flag for the end of a word:

class TrieNode:
    def __init__(self):
        self.children = {}  # letter -> TrieNode
        self.end = False    # does a stored word end here?

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.end = True

Notice that the node never stores its own letter or its prefix: the letter is the key in the parent’s dict. The figures write the prefix inside each node only to help you read them.

Another common way is an array of 26 children, one per letter a to z, with None where there is no child. In C or Java this is faster than a hash table. In Python a dict is simpler and usually uses less memory, because most nodes have only one or two children.

Cost and memory

Inserting or finding a word of length L takes L steps, one per letter, and each step is one dict lookup, which takes O(1) time on average (HASH). So both cost O(L). The number of stored words, n, does not appear at all. A trie with a million words answers as fast as a trie with ten.

Compare a sorted list of n words: binary search makes about log₂ n string comparisons (how many times you can halve n), and each comparison can read up to L letters, so O(L log n). A set is also O(L), because hashing a string reads all of its letters, but a set cannot answer prefix questions.

The price is memory. The trie has one node for each different prefix, so at most N + 1 nodes, where N is the total number of letters in all the words. In Python each node is an object with its own dict, a few hundred bytes. That is much more than the string itself. Lesson 4 shows how to cut the number of nodes.