Tries and prefix trees

Node-per-character layout, insert and prefix search, the memory cost of wide alphabets, compressed and radix variants, and the autocomplete patterns tries exist for.

One node per character

A trie stores strings by their characters rather than by their hash. Shared prefixes share nodes, which makes prefix operations natural instead of a scan over every key.

insert: car, cart, cat, dog

        (root)
        /    \
       c      d
       |      |
       a      o
      / \     |
     r   t    g*
     |   |
     t*  (end)
     |
    (end)

* marks a terminal node: a complete word ends here

class Trie:
    __slots__ = ("children", "is_word")
    def __init__(self):
        self.children = {}
        self.is_word = False

    def insert(self, word):
        node = self
        for ch in word:
            node = node.children.setdefault(ch, Trie())
        node.is_word = True

    def starts_with(self, prefix):
        node = self
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return False
        return True

The memory bill

Alphabet	Fixed array per node	Typical waste
Lowercase a-z (26)	26 pointers per node	Most pointers are null
ASCII (128)	128 pointers per node	Severe unless dense
Unicode	Impossible to array	Use a hash map per node
Compressed (radix)	Multi-character labels	Far fewer nodes

An array per node is fast but memory-hungry; a dict per node is compact but slower and allocates more.
A radix or Patricia trie merges chains of single-child nodes into one edge labelled with a substring.
A DAWG or minimal automaton merges identical suffixes as well as prefixes, shrinking dictionaries enormously.
Storing values at terminal nodes turns the trie into an ordered map keyed by string.

# collect all completions under a prefix
def completions(node, prefix, out, limit=10):
    if len(out) >= limit:
        return
    if node.is_word:
        out.append(prefix)
    for ch, child in sorted(node.children.items()):
        completions(child, prefix + ch, out, limit)
        if len(out) >= limit:
            return

Where tries earn their place

Use case	Why a trie	Alternative
Autocomplete	Prefix search without scanning all keys	Sorted array plus binary search on the prefix
Spell check and fuzzy match	Bounded edits from a prefix state	BK-tree, Levenshtein automaton
IP routing (longest prefix match)	Bitwise prefix traversal	Compressed prefix trees in hardware
Word games and solvers	Shared prefixes prune the search	Brute force is fine for tiny dictionaries
Blocking sensitive terms	Scan input in one pass	Aho-Corasick automaton for many patterns

⚠️

A trie is not automatically faster than a hash set. Lookup has the same O(key length) cost as hashing, but with worse cache behaviour and much higher memory use. Choose it for prefix queries, not for plain membership tests.

FAQ

When should I use a radix trie?

When the keys share long prefixes or the alphabet is large. Compressing single-child chains into labelled edges cuts node count dramatically, which is what makes routing tables and large dictionaries practical.

How do I make autocomplete rank results?

Store a score or a small top-k list at each node, updated on insert. That turns completion into reading a precomputed list instead of traversing the whole subtree.

Sets, maps and the abstract data type view Probabilistic structures: Bloom filters and skip lists

Last refreshed 2026-09-18.

Tries and prefix trees

One node per character

The memory bill

Where tries earn their place

FAQ

Related