How to Implement a Trie for Autocomplete: A Practical Guide

Autocomplete is everywhere. Search bars, messaging apps, code editors, and command lines all suggest completions as you type. Behind the scenes, many of these systems rely on a trie data structure. A trie, also called a prefix tree, is purpose-built for storing strings and efficiently looking up all strings that share a common prefix. In this guide, I’ll show you how to implement a trie from scratch, build an autocomplete feature on top of it, and optimize it for real-world use. By the end, you’ll have a working autocomplete engine you can adapt to any language.

What Is a Trie and Why Use It for Autocomplete?

A trie is a tree where each node represents a single character. The root node is empty. Each path from the root to a leaf spells out a stored string. Nodes have a flag marking whether they represent the end of a word. This structure makes prefix searches blazing fast: you just walk down the characters of the prefix, then collect all words below that node.

Why not use a hash set or list? A hash set can check whether a full word exists in O(1) average time, but it cannot find all words with a given prefix without scanning every entry. A trie solves that. Insertion and search are both O(n) where n is the length of the word. That’s acceptable for most use cases, and the ability to retrieve prefixes makes it unbeatable for autocomplete.

Step-by-Step: Building a Trie in Python

Let’s implement a simple trie using Python dictionaries. Each node will have two fields: children (a dict mapping characters to child nodes) and is_end (a boolean indicating a complete word).

Defining the Trie Node

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

That’s it. Each node can have up to 26 children for basic English letters, but using a dictionary allows any Unicode character and saves memory for sparse trees.

Inserting Words

Insertion traverses the trie character by character, creating nodes as needed, and marks the last node as an end-of-word.

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

Each insertion runs in O(m) time, where m is the word length. Memory grows with the number of unique prefixes.

Searching for a Word

Searching follows the same path. If we reach the end of the word and the node’s is_end is True, the word exists.

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

Implementing Autocomplete: Finding All Words with a Prefix

Autocomplete needs to return all words that start with a given prefix. First, we walk down the trie to the node representing the last character of the prefix. If that node doesn’t exist, there are no suggestions. Then we perform a depth-first search (DFS) from that node, collecting words along the way.

We can track the current prefix string as we descend. When we reach a node with is_end = True, we add the accumulated string to the results.

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

def _dfs(self, node, prefix):
    words = []
    if node.is_end:
        words.append(prefix)
    for ch, child in node.children.items():
        words.extend(self._dfs(child, prefix + ch))
    return words

This simple DFS returns all suggestions in lexicographic order if we iterate children in sorted order. For a trie with many words, DFS can return a large list, so you may want to limit the number of suggestions (e.g., 10).

Optimizing for Real-World Use

Basic tries work well for small dictionaries, but real autocomplete systems need to handle millions of words, memory constraints, and fast response times. Here are some optimizations.

Limiting the Number of Suggestions

Modify DFS to stop after collecting a maximum number of results. This avoids returning thousands of words when the prefix is short.

def _dfs(self, node, prefix, limit, results):
    if len(results) >= limit:
        return
    if node.is_end:
        results.append(prefix)
    for ch in sorted(node.children):
        if len(results) >= limit:
            break
        self._dfs(node.children[ch], prefix + ch, limit, results)

Memory Efficient Storage

Using a dictionary per node adds overhead. For fixed alphabets, you can use an array of size 26 (or the character set size) where each entry is either None or a reference to the child node. For example, self.children = [None] * 26 and index by ord(ch) - ord('a'). This trades memory for speed, especially when the tree is dense.

Compressed Tries (Radix Trees)

A compressed trie merges nodes with single children into a single node, reducing memory and traversal steps. Implementations are more complex but useful for large static dictionaries.

Weighted Suggestions

Real autocomplete engines rank suggestions by frequency or recency. Store a weight or score at each end-of-word node. When collecting suggestions, return them sorted by weight.

Comparison: Trie vs Alternatives for Autocomplete

Data Structure	Prefix Search Speed	Memory Usage	Use Case
Trie	O(n + k) where k is number of suggestions	High (node overhead)	Medium dictionaries, need prefix search
Hash Set	O(n) per lookup, no prefix search	Low	Exact word lookup only
Sorted Array + Binary Search	O(m log N) for prefix via binary search	Low	Static dictionaries, updates rare
Ternary Search Tree	O(n + k) average	Medium	Memory-constrained, dynamic

Tries excel when you need frequent prefix lookups and the dictionary changes often. For static sets, a sorted array with binary search might be simpler and memory-efficient.

Common Mistakes and How to Avoid Them

1. Forgetting the end-of-word flag. Without it, you can’t distinguish between a full word and a prefix that’s part of another word. Always mark nodes.

2. Case sensitivity. By default, ‘A’ and ‘a’ are different characters. Normalize words to lowercase before insertion and search.

3. Ignoring memory. Each node with a dict of children consumes a lot of memory. For large dictionaries, use an array or a compact representation.

4. Not limiting results. Autocomplete that returns hundreds of suggestions is useless. Always cap the number, and consider ranking by popularity.

5. Recursion depth. Deep tries can cause recursion limits in Python. Use an iterative stack-based DFS instead of recursion for production code.

Iterative DFS for Autocomplete (Avoiding Recursion Limits)

Here’s an iterative version using a stack of (node, prefix) tuples:

def autocomplete_iter(self, prefix):
    node = self.root
    for ch in prefix:
        if ch not in node.children:
            return []
        node = node.children[ch]
    
    results = []
    stack = [(node, prefix)]
    while stack and len(results) < 10:
        node, path = stack.pop()
        if node.is_end:
            results.append(path)
        for ch in sorted(node.children, reverse=True):
            stack.append((node.children[ch], path + ch))
    return results

Using reverse=True simulates lexicographic order without sorting the entire stack. This method easily handles large dictionaries.

Now you have a complete understanding of how to implement a trie for autocomplete. Start with the basic structure, add prefix traversal, optimize with limits and memory tricks, and choose the right data structure for your scale. For more detailed implementation tips and code examples, check out the full guide: Implement a Trie for Autocomplete: A Step-by-Step Guide.

Happy coding!

Frequently asked questions

What is a trie data structure?

A trie is a tree-like data structure that stores strings by their characters. Each node represents a character, and paths from the root to nodes spell out words. It enables fast prefix lookups, making it ideal for autocomplete, spell checkers, and IP routing.

How does a trie work for autocomplete?

A trie stores all dictionary words. When a user types a prefix, you traverse the trie to the node representing that prefix, then perform a depth-first search to collect all words under that node. The search is O(n + k) where n is prefix length and k is number of suggestions.

What is the time complexity of trie operations?

Insertion and search are O(m), where m is the length of the word. Autocomplete requires O(n + k) time: O(n) to traverse the prefix and O(k) to collect suggestions. These are linear in input size and independent of total dictionary size.

How do you handle uppercase and lowercase in a trie?

Standard tries are case-sensitive. For autocomplete, convert all words and user input to a single case (usually lowercase) before inserting or searching. This ensures consistent matching.

Can a trie be used for languages other than English?

Yes. Use a dictionary for children instead of a fixed array, as Unicode characters vary widely. You can also encode UTF-8 byte sequences. Tries work for any alphabet or script.

What are the memory limitations of a trie?

Each node stores a reference to children, which adds overhead. For large alphabets (e.g., Unicode), a dict per node is memory-intensive. Alternatives include arrays (for small fixed sets) or compressed tries (radix trees) to reduce node count.

How do you limit the number of autocomplete suggestions?

Modify your DFS to stop after collecting a maximum number of results. Pass a counter or limit parameter, and break recursion once the limit is reached. Alternatively, use an iterative stack that checks the limit each iteration.

What is the difference between a trie and a ternary search tree?

A ternary search tree (TST) uses three child pointers per node (less, equal, greater) instead of a full alphabet. TSTs use less memory when the alphabet is large but have slightly slower lookups due to comparisons. Tries are faster for dense prefixes; TSTs are more memory-efficient.