Trie Data Structure: Prefix Trees and Auto-Complete

Algorithms Algorithms 8 min read 1536 words Beginner ExcellentWiki Editorial Team

A trie (pronounced “try”), also called a prefix tree, is a tree data structure that stores strings by their common prefixes. Unlike binary search trees where each node holds a full key, each node in a trie represents a single character, and a path from root to a node spells out a prefix of a stored string.

Tries excel at prefix-based lookups — checking whether a word exists, finding all words with a given prefix, and computing longest common prefixes — all in O(k) time where k is the length of the string, independent of how many strings are stored.

Structure and Representation

Every trie node contains:

An array or map of child nodes (one per possible next character)
A flag indicating whether the node represents the end of a complete word

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

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.is_end = True

    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_end

    def starts_with(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True

The children can be stored as a fixed-size array (size 26 for lowercase English) for O(1) lookups at the cost of memory, or as a hash map for flexibility. The array approach is faster but wastes space for sparse alphabets. Hybrid approaches — like using arrays for dense layers and maps for sparse ones — are common in production systems.

Autocomplete

Given a prefix, find all complete words that share that prefix. The algorithm follows the prefix to its node, then performs a DFS from that node collecting every complete word.

def autocomplete(self, prefix):
    node = self.root
    for ch in prefix:
        if ch not in node.children:
            return []
        node = node.children[ch]
    result = []
    self._collect_words(node, prefix, result)
    return result

def _collect_words(self, node, prefix, result):
    if node.is_end:
        result.append(prefix)
    for ch, child in sorted(node.children.items()):
        self._collect_words(child, prefix + ch, result)

The result set includes every word in the subtree. For a trie with millions of words, this can return hundreds of completions. To limit results for an autocomplete UI, stop after collecting the top K results (by frequency or alphabetically).

In production autocomplete systems, each node may also store a ranked list of popular completions at that prefix. This pre-computation avoids traversing the subtree on every keystroke and enables sorted-by-frequency results. Search engines like Google and Bing use variants of this approach, combining trie-based prefix matching with frequency-ranked suggestions that incorporate user history and trending queries.

Spell Check and Correction

A trie supports simple spell checking by testing search(word). For correction, use a recursive search that allows edits (deletions, insertions, substitutions) — essentially a Levenshtein distance or Damerau-Levenshtein distance traversal.

def search_with_edits(self, word, max_edits=2):
    results = []

    def dfs(node, prefix, remaining, edits):
        if not remaining:
            if node.is_end:
                results.append((prefix, edits))
            return
        if edits > max_edits:
            return
        ch = remaining[0]
        if ch in node.children:
            dfs(node.children[ch], prefix + ch, remaining[1:], edits)
        # substitution
        for next_ch in node.children:
            if next_ch != ch:
                dfs(node.children[next_ch], prefix + next_ch, remaining[1:], edits + 1)
        # deletion
        dfs(node, prefix, remaining[1:], edits + 1)
        # insertion
        for next_ch in node.children:
            dfs(node.children[next_ch], prefix + ch + next_ch, remaining, edits + 1)

    dfs(self.root, "", word, 0)
    return sorted(results, key=lambda x: x[1])[:10]

This is a simplified correction search. Real spell checkers use a combination of tries and BK-trees (Burkhard-Keller trees), or rely on SymSpell, which exploits the fact that most misspellings involve small edit distances and pre-computes deletions. SymSpell achieves constant-time lookup for edit distance 1 and 2 by generating all possible deletion variants of each dictionary word at build time, trading memory for raw speed.

Prefix Compression

A radix tree (or Patricia trie) compresses paths where nodes have only one child into a single edge labeled with the full string. This reduces the number of nodes drastically when storing long strings with shared prefixes.

# Standard trie:   r -> e -> s -> t
# Radix tree:      rest

Radix trees are used in:

Linux kernel (the rbtree data structure is unrelated; the kernel uses radix trees for page cache indices)
Redis (for its RDB persistence, and internally for radix tree-based data structures)
IP routing (longest prefix match in CIDR tries)

The trade-off is more complex insertion and deletion logic, since edges can contain multi-character strings and may need to be split when a new word shares only part of a compressed edge.

Complexity Analysis

Operation	Trie	Hash Table	BST
Insert	O(k)	O(k) avg	O(k log n)
Search	O(k)	O(k) avg	O(k log n)
Prefix search	O(k + m)	O(n)	O(k + m) worst
Delete	O(k)	O(k) avg	O(k log n)

Where k is the key length, m is the number of matches for prefix search, and n is the total number of keys.

The critical advantage of a trie is that prefix queries are fast and there are no hash collisions. The critical disadvantage is memory — each character of each unique prefix requires a node with pointer overhead.

Memory Optimization

A standard trie storing 100,000 English words can consume 5–10 MB. Several techniques reduce this:

Ternary search tries: Each node has three children (less than, equal, greater), reducing per-node storage at the cost of slightly slower lookups. TSTs combine the time efficiency of tries with the space efficiency of binary search trees, making them popular in autocomplete systems for mobile keyboards where memory is constrained.
Double-array tries: Represent the trie in two parallel arrays for cache-efficient traversal — used in projects like mecab and libdatrie. Double-array tries combine the speed of array-based nodes with the memory efficiency of compressed representations, making them the fastest structure for dictionary lookup in NLP pipelines.
Compressed (radix) tries: Merge single-child paths to dramatically reduce node count.
Array-based nodes: Use fixed arrays for dense alphabets at intermediate levels, map-based nodes for sparse leaf levels.

Applications

Autocomplete — search engines, IDEs, mobile keyboards
Spell checking — word processors, browsers
IP routing — longest prefix match in routers
Dictionary representation — Scrabble word lookup, word games
Genome analysis — substring search in DNA sequences (especially in bioinformatics tools based on suffix tries/arrays)
Compressed data structures — FM-index uses a variant of the trie for substring search in compressed text
Natural language processing — morphological analysis, part-of-speech tagging using lexicon lookup
Predictive text entry — used in assistive technology for users with motor disabilities

In competitive programming, tries are frequently the optimal data structure when the input size is large and the alphabet is small (like lowercase letters or binary), because the linear-time prefix lookups beat logarithmic-time binary search trees for these workloads.

Comparison with Alternative Data Structures

The choice between a trie and other data structures depends on the specific requirements. Hash tables provide faster average-case exact-match lookups and use less memory, but cannot support prefix queries at all. Binary search trees support ordered iteration and range queries, but prefix queries require scanning. Suffix trees, while more complex, support powerful substring queries over a single text. Bloom filters offer space-efficient membership testing with false positives but no prefix support. In practice, production systems often combine multiple structures — for example, a trie for prefix autocomplete backed by a hash set for exact-match confirmation.

FAQ

What is the difference between a trie and a hash table? Tries support prefix-based queries (find all strings starting with a given prefix) in O(k + m) time, where k is the prefix length and m is the number of matches. Hash tables cannot support prefix queries efficiently. Tries also have no hash collisions and their performance is deterministic. However, hash tables use less memory and have faster average-case lookups for exact matches.

When should I use a trie versus a binary search tree? Use a trie when you need prefix queries, the keys are strings with a small alphabet, and you need consistent O(k) lookup time. Use a BST when keys are not strings or when you need ordered traversal of the full key space.

How much memory does a trie use? A standard trie for 100,000 English words requires 5–10 MB. Each node typically costs 24–48 bytes depending on the implementation. Compressed (radix) tries and double-array tries can reduce this to 1–3 MB for the same dataset.

Can a trie handle Unicode strings? Yes. Instead of a 26-element array, use a hash map for children. Each node maps a Unicode code point or character to its child node. This works for any alphabet but increases per-node memory overhead. For CJK characters, consider using a different data structure like a B-tree optimized for wide alphabets.

What is the difference between a trie and a suffix tree? A trie stores a set of strings. A suffix tree stores all suffixes of a single string in a compressed trie, enabling O(m) substring search where m is the query length. Suffix trees are more complex to build (O(n) using Ukkonen’s algorithm) but support powerful string operations like longest repeated substring and longest common substring.