Implement a Trie for Autocomplete: A Step-by-Step Guide

Autocomplete is one of those features that feels almost magical until you understand how it works. When you type a few letters into a search bar or code editor, the system predicts what you’re trying to say. The key data structure behind most autocomplete systems is the trie (also called a prefix tree). In this guide, I’ll walk through how to implement a trie for autocomplete from scratch, with code examples you can use in your own projects.

What Is a Trie and Why Use It for Autocomplete?

A trie is a tree-like data structure where each node represents a single character of a string. Strings with the same prefix share the same path of nodes. This makes tries extremely efficient for prefix-based searches, which is exactly what autocomplete does.

Compared to using a list or a set, a trie can find all words matching a prefix in time proportional to the prefix length plus the number of matches, rather than scanning every word. For large dictionaries (like tens of thousands of words), this is a huge performance win. The trade-off is memory: each node stores a dictionary of children, which can add up. But for most real-world autocomplete needs, the memory is acceptable.

Core Trie Node Structure

Every trie node needs two things: a way to store its children (typically a dictionary or hash map) and a flag indicating whether this node marks the end of a word. Here’s a simple Python class:

class TrieNode:
    def __init__(self):
        self.children = {}  # character -> TrieNode
        self.is_end = False

Some implementations also store a reference to the parent or the character itself, but those are optional. This minimal structure is all we need for autocomplete.

Inserting Words into the Trie

Insertion is straightforward: iterate over each character in the word, moving to the child node (creating it if it doesn’t exist), and finally mark the last node as an end-of-word.

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

Notice that we don’t store the word itself anywhere. The trie encodes the words as paths. This is what makes prefix queries fast: you follow the path and then explore from there.

Searching for a Word

A basic search returns True if the exact word exists in the trie. We traverse characters and check if the final node is marked as an end-of-word. If at any point a character is missing, return False.

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

Implementing Autocomplete: Finding Words with a Prefix

The real power of the trie shines here. To get autocomplete suggestions for a prefix, we do two steps:

1. Traverse the trie following the characters of the prefix. If we can’t complete the traversal, there are no suggestions.
2. From the node where the prefix ends, perform a depth-first search (DFS) to collect all complete words in that subtree.

Here’s the code:

def autocomplete(self, prefix):
    node = self.root
    for char in prefix:
        if char not in node.children:
            return []  # no suggestions
        node = node.children[char]
    # Now collect all words from this node
    self._words = []
    self._dfs(node, prefix)
    return self._words

def _dfs(self, node, prefix):
    if node.is_end:
        self._words.append(prefix)
    for char, child in node.children.items():
        self._dfs(child, prefix + char)

This collects all words that start with the given prefix. For very large subtrees, you might limit the number of results (e.g., top 10), but the principle is the same. One thing to watch: if your dictionary has many words sharing a long common prefix, the DFS could be expensive. You can stop early by tracking a counter and returning after enough results.

Optimizing and Extending the Trie

The basic trie works, but there are common improvements. One is to store the complete word at the end node instead of rebuilding it during DFS. This trades memory for speed. Another optimization is to compress the trie into a radix tree (or Patricia trie), where single-child chains are merged. For autocomplete, however, the standard trie is usually fine.

You can also add a frequency counter to each node to rank suggestions. When inserting, increment a counter on each node along the path. During autocomplete, you can use that counter to sort results by popularity. A simple way: store a list of the top k words directly at each node, updating it during insertion. This makes autocomplete O(L + K) but increases insertion cost. Decide based on whether your workload is read-heavy or write-heavy.

Comparison: Trie vs. Other Autocomplete Approaches

Approach	Insert Time	Search Time	Autocomplete Time	Memory
List/Array	O(1)	O(N)	O(N) per prefix	Low
Binary Search Tree	O(log N)	O(log N)	O(K + log N)	Medium
Trie	O(L)	O(L)	O(L + M)	High

N = number of words, L = length of word/prefix, M = number of matches, K = size of result set. The trie wins for autocomplete because prefix traversal is O(L), and collecting matches visits only relevant nodes. For a list, you’d have to scan every word, which gets slow with large dictionaries. A BST is better but still requires O(log N) per prefix traversal and extra overhead for collecting matches.

Common Pitfalls and How to Avoid Them

One mistake is forgetting to mark the end of a word. Without it, search returns true for prefixes that are not actual words. Another issue is case sensitivity — decide upfront whether to lowercase all inputs. Also, be careful with Unicode characters; the children dictionary can handle them natively, but encoding can add complexity. For instance, if you store characters as bytes vs. strings, you might get collisions. Stick with Python strings for simplicity.

Another pitfall is memory leaks from unused nodes. If you delete words, you should prune nodes that have no children and aren’t end nodes themselves. Otherwise, deleted words still consume memory. Pruning requires either reference counting or a recursive cleanup from the parent. It’s an advanced topic but worth considering for long-lived tries.

Putting It All Together: A Full Example

Here’s a complete example that creates a trie, inserts words, and performs autocomplete:

def main():
    words = ["hello", "help", "he", "hero", "her", "high", "heat"]
    trie = Trie()
    for w in words:
        trie.insert(w)
    print(trie.autocomplete("he"))  # Output: ['hello', 'help', 'he', 'hero', 'her', 'heat']
    print(trie.search("hi"))        # False

You can modify this to limit results, add ranking, or support deleting words (by clearing the end flag and pruning empty nodes). If you want to limit the number of suggestions, change the DFS to accept a maximum count and stop early. For ranking, store a list of (word, frequency) at each node and update it on insertion.

One real-world consideration: if your autocomplete needs to handle misspellings or fuzzy matching, a regular trie won’t suffice. You’d need to extend it with Levenshtein distance or use a BK-tree. But for exact prefix matching, the trie is hard to beat.

When Not to Use a Trie

Tries aren’t always the best choice. If your dictionary is small (a few hundred words), a simple list with substring matching might be faster to implement and fast enough. If you need frequent deletions and insertions, a balanced BST or a hash set with prefix indexing could be simpler. Tries also struggle with memory when the alphabet is large (e.g., all Unicode characters). In that case, you might use a ternary search tree or a hash map-based approach. For most autocomplete features in web apps or editors, though, the trie is a strong default.

Frequently asked questions

What is a trie data structure?

A trie is a tree-like data structure that stores strings by their common prefixes. Each node represents a character, and paths from root to leaf represent words. It allows fast prefix-based searches, making it ideal for autocomplete.

How does a trie work for autocomplete?

Words are inserted character by character, creating nodes as needed. To autocomplete a prefix, you traverse the trie to the node at the end of the prefix, then perform a depth-first search to collect all words in that subtree.

What are the time complexities of trie operations?

Insertion and search both take O(L) time where L is the length of the word. Autocomplete takes O(L + M) where M is the number of matching words. This is much faster than scanning a list.

What are the main disadvantages of a trie?

Tries can consume a lot of memory because each node stores a dictionary of children. For large alphabets or many words, memory usage can be high. Compressed tries (radix trees) help mitigate this.

Can a trie handle large dictionaries?

Yes, tries are well-suited for large dictionaries (hundreds of thousands of words) because search time depends only on word length, not dictionary size. Memory, however, needs to be managed.

How do I limit autocomplete results to a certain number?

During the DFS traversal, you can stop after collecting K results. Pass a counter and break early when it reaches the limit. You can also use a priority queue to return top K by frequency.

How do I add frequency ranking to trie autocomplete?

Add an integer counter to each node. When inserting a word, increment the counter on every node along the path. During autocomplete, collect nodes with their counts and sort before returning.

What programming languages can I implement a trie in?

Tries can be implemented in any language that supports dynamic data structures, including Python, Java, C++, JavaScript, and Go. The core concepts are language-agnostic.