Trie (Prefix Tree)

A tree keyed on shared prefixes that stores a set of strings for fast prefix search, autocomplete, and dictionary lookup.

Structure

A trie is a rooted tree where each edge is labelled by one symbol from an alphabet. A path from the root spells a prefix; nodes flagged as terminal mark complete stored words. Lookup, insertion, and prefix enumeration take O(L) time in the length L of the key, independent of how many keys are stored.

Where it wins

Kronos motion — classical

Because branches share common prefixes, a trie answers autocomplete (all words starting with a prefix) and longest-prefix-match (routing tables, IP lookup) directly by walking the prefix path. Unlike a hash set, it enumerates keys in sorted order and supports prefix range queries without extra structure.

Insertion and search

python

class Node:
    __slots__ = ('kids','end')
    def __init__(self):
        self.kids = {}
        self.end = False

root = Node()

def insert(word):
    node = root
    for ch in word:
        node = node.kids.setdefault(ch, Node())
    node.end = True

def contains(word):
    node = root
    for ch in word:
        node = node.kids.get(ch)
        if node is None:
            return False
    return node.end

Space-efficient variants

Compressed trie (radix/Patricia tree) collapses chains of single-child nodes into one edge with a string label.
Ternary search trees store children as a small BST, saving space on sparse alphabets.
Double-array and succinct tries pack the structure into flat arrays for cache-friendly, read-only dictionaries.
A DAWG (directed acyclic word graph) merges identical suffixes to shrink the automaton further.

Related machines

Adding failure links to a trie yields the Aho-Corasick automaton for multi-pattern matching. Minimizing a suffix trie gives a suffix automaton.