Tries and Prefix Trees

1The letters live on the edges

Every other tree in this course stores data in the nodes. A trie stores it on the edges, and that single change is what makes it work.

In a trie (from retrieval, and usually pronounced “try” to distinguish it from “tree”), a node's identity is the path taken to reach it. The node itself stores almost nothing: a map from character to child, and one boolean saying “a stored word ends here.”

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

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

2Insert, search, starts-with

All three are the same walk down the tree. They differ only in what they do when the path runs out.

def insert(self, word):
    node = self.root
    for ch in word:
        if ch not in node.children:
            node.children[ch] = TrieNode()    # create only if missing
        node = node.children[ch]
    node.is_word = True                       # mark the end


def search(self, word):
    node = self._walk(word)
    return node is not None and node.is_word  # the FLAG decides


def starts_with(self, prefix):
    return self._walk(prefix) is not None     # merely arriving is enough


def _walk(self, s):
    """Follow s from the root. Returns the node, or None if the path breaks."""
    node = self.root
    for ch in s:
        if ch not in node.children:
            return None
        node = node.children[ch]
    return node

The difference between search and starts_with is one clause, and it is exactly the distinction the is_word flag exists to make.

m = the length of the key.

3Autocomplete

The operation tries exist for. Once you have walked the prefix, the answer is simply everything below you.

Every descendant of the node at the end of a prefix shares that prefix — that is what “the path is the key” means. So autocomplete is two steps: walk the prefix, then collect the subtree.

def completions(self, prefix, limit=None):
    node = self._walk(prefix)
    if node is None:
        return []                       # no word has this prefix at all

    out = []
    def collect(n, path):
        if limit is not None and len(out) >= limit:
            return
        if n.is_word:
            out.append(prefix + path)
        for ch in sorted(n.children):   # sorted → results in alphabetical order
            collect(n.children[ch], path + ch)

    collect(node, "")
    return out

# Cost: O(m) to walk the prefix, plus O(size of the subtree) to collect.
# Note what is NOT in that cost: the number of words in the trie.

A real autocomplete wants the best completions, not the alphabetically first. The standard extension: store a frequency or score on each word-ending node, and either collect everything and take the top k with a heap (Chapter 17), or cache the best few completions at every node so the answer is available immediately.

class RankedTrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False
        self.score = 0
        self.top = []      # cached best completions of this node's prefix

# Google's search box does the second thing. The cache costs memory and
# must be updated on insert, and in exchange the query is O(m) with no
# subtree walk at all — which matters when the subtree is a million words.

4What a trie costs

Tries are fast and they are expensive. Being honest about the second part is what stops you reaching for one when a hash table would do.

A trie allocates a node per character per distinct prefix. In Python each node is an object with a dictionary, which is roughly 100–250 bytes before you store anything.

The saving grace is prefix sharing. car, card, care and cart share three nodes rather than storing twelve characters. On data with heavy shared prefixes — URLs, file paths, IP prefixes, DNA — the ratio flips and a trie can be smaller than the raw strings.

The compressed trie

Most of the waste is chains of single-child nodes. A radix tree collapses each chain into one edge labelled with the whole substring:

# Plain trie for ["romane", "romanus", "romulus"]:
#   r - o - m - a - n - e
#                 \    \- u - s
#                  \- u - l - u - s
#   13 nodes, most with exactly one child.

# Radix tree — collapse every single-child chain:
#   "rom" - "an" - "e"
#      \        \- "us"
#       \- "ulus"
#   5 nodes.

# Same operations, same asymptotic costs, a fraction of the memory.
# This is what IP routing tables and Git's object store actually use.

5Where tries actually get used

Five real systems, and the one property each of them needs.

1. IP routing

A router must find the longest matching prefix for a destination address: 192.168.1.0/24 should win over 192.168.0.0/16. Walk the address bit by bit and remember the deepest node marked as a route. Hash tables cannot do this at all — you would have to try all 32 prefix lengths separately.

2. Autocomplete and search suggestions

The obvious one. Walk the prefix, read the subtree, ranked by a stored score.

3. Spellcheck and fuzzy matching

Walk the trie while allowing a bounded number of mismatches. Because the whole subtree is pruned the moment the error budget runs out, this is dramatically faster than comparing against every dictionary word.

def fuzzy_search(node, word, i, edits, prefix, out):
    """All stored words within `edits` substitutions of `word`."""
    if edits < 0:
        return                                  # ← the pruning IS the algorithm
    if i == len(word):
        if node.is_word:
            out.append(prefix)
        return
    for ch, child in node.children.items():
        cost = 0 if ch == word[i] else 1
        fuzzy_search(child, word, i + 1, edits - cost, prefix + ch, out)

# Every wrong branch dies as soon as the budget is exhausted, so most of
# the dictionary is never visited.

4. Word games and puzzle solvers

A Boggle or Scrabble solver walks the board and the trie simultaneously. The moment the letters so far are not a prefix of any word, the entire branch of the search is abandoned. Without that pruning the search space is impossible.

5. Compilers and text editors

Keyword recognition, syntax highlighting and symbol completion are all prefix problems.

>_Playground

A full trie with autocomplete and fuzzy search. Compare its memory against a plain set, and watch the pruning at work.

✓Exercises

Checked automatically the moment you submit. Work top to bottom — each one assumes the last. Your answers are saved in this browser.