Tries and Prefix Trees

Updated

October 31, 2026

Tries and Prefix Trees

A Trie (derived from “retrieval”), also known as a prefix tree, is a specialized tree structure where each edge represents a single character in a string key. Descendant nodes share the common string prefix of their parents. While standard Python dictionaries provide fast exact lookups, a Trie performs prefix matching, autocompletion, and dictionary validation in \(O(L)\) time, where \(L\) is the character length of the query, regardless of whether your catalog has ten items or ten million.

Mental model

In a Trie, individual characters label the transitions between nodes. Terminal markers designate where valid complete words end:

                  (Root)
                 /      \
               "c"      "t"
               /          \
             "a"          "e"
            /   \           \
          "r"   "t"         "a"
           |     |           |
        (cart) (cat)       (tea)
  • Prefix Sharing: The words "cart" and "cat" share the nodes for "c" and "a".
  • Search Complexity: Searching for "cat" requires traversing 3 character hops. Its complexity is \(O(L)\), completely independent of the number of words stored in the tree.
  • Autocompletion: Traverse to the end of the query prefix, then perform a depth-first traversal of all descendant nodes marked as terminal words.

Worked examples

Case 1: Catalog SKU and Keyword Autocomplete

Save as trie_catalog.py. Build a Trie for desk equipment SKUs that provides prefix matching and autocompletion recommendations.

# trie_catalog.py
from dataclasses import dataclass, field


class TrieNode[T]:
    def __init__(self, value: T | None = None) -> None:
        self.children: dict[str, TrieNode[T]] = {}
        self.is_terminal: bool = False
        self.value: T | None = value


class Trie[T]:
    def __init__(self) -> None:
        self.root: TrieNode[T] = TrieNode()
        self._count = 0

    def insert(self, word: str, value: T | None = None) -> None:
        curr = self.root
        for ch in word:
            if ch not in curr.children:
                curr.children[ch] = TrieNode()
            curr = curr.children[ch]
        if not curr.is_terminal:
            self._count += 1
        curr.is_terminal = True
        curr.value = value

    def search(self, word: str) -> T | None:
        curr = self.root
        for ch in word:
            if ch not in curr.children:
                return None
            curr = curr.children[ch]
        if curr.is_terminal:
            return curr.value
        return None

    def starts_with(self, prefix: str) -> bool:
        curr = self.root
        for ch in prefix:
            if ch not in curr.children:
                return False
            curr = curr.children[ch]
        return True

    def autocomplete(self, prefix: str) -> list[tuple[str, T | None]]:
        curr = self.root
        for ch in prefix:
            if ch not in curr.children:
                return []
            curr = curr.children[ch]

        results: list[tuple[str, T | None]] = []

        def _collect(node: TrieNode[T], path: str) -> None:
            if node.is_terminal:
                results.append((path, node.value))
            for char, child in sorted(node.children.items()):
                _collect(child, path + char)

        _collect(curr, prefix)
        return results


def main() -> None:
    catalog: Trie[str] = Trie()
    catalog.insert("DESK-LAMP", "Adjustable 24W LED Lamp")
    catalog.insert("DESK-MAT", "Waterproof Vegan Leather Pad")
    catalog.insert("DESK-CHAIR", "Ergonomic Lumbar Office Chair")
    catalog.insert("DESK-CLOCK", "Minimalist Digital Desk Clock")
    catalog.insert("DISH-TOWEL", "Absorbent Microfiber Kitchen Towel")

    # Exact Search
    sku = "DESK-LAMP"
    item = catalog.search(sku)
    print(f"Exact SKU search for '{sku}': {item}")

    # Prefix check
    prefix = "DESK-"
    has_prefix = catalog.starts_with(prefix)
    print(f"Any items starting with '{prefix}'? {has_prefix}")

    # Autocompletion
    print(f"\nAutocomplete recommendations for '{prefix}':")
    for matched_sku, description in catalog.autocomplete(prefix):
        print(f"  • {matched_sku}: {description}")


if __name__ == "__main__":
    main()

Run:

uv run python trie_catalog.py

Output:

Exact SKU search for 'DESK-LAMP': Adjustable 24W LED Lamp
Any items starting with 'DESK-'? True

Autocomplete recommendations for 'DESK-':
  • DESK-CHAIR: Ergonomic Lumbar Office Chair
  • DESK-CLOCK: Minimalist Digital Desk Clock
  • DESK-LAMP: Adjustable 24W LED Lamp
  • DESK-MAT: Waterproof Vegan Leather Pad

The trap

The memory overhead trap: In Python, every dictionary consumes hundreds of bytes of hash table memory. Storing 500,000 words in a naive Trie where every node contains a dict[str, TrieNode] can consume gigabytes of memory.

If memory footprint is paramount, compress long non-branching sequences into single multi-character edges (a Radix Tree / Patricia Trie), or use the Python standard library’s sqlite3 in-memory module with LIKE 'prefix%' indexing.

The boring rule

  1. Use Python’s built-in dict when looking up complete exact strings.
  2. Use a Trie when your application specifically requires prefix filtering, predictive autocompletion, or IP routing lookups.
  3. Represent child transitions using standard Python dictionaries (self.children: dict[str, TrieNode]) to automatically support UTF-8 runes and non-ASCII character sets without string bounds crashes.
  4. Limit autocompletion depth or gather suggestions lazily using a generator if the catalog contains millions of candidate suffixes.

Try this

  1. Add a delete(word: str) -> bool method to Trie that unsets is_terminal and deletes child branches that have no other terminal descendants.
  2. Build an in-memory spell-check validator that flags whether an input word exists in a dictionary and suggests words sharing a prefix.