Stimulate TRIE data structure

How to Build a Fast Search-as-You-Type Autocomplete Engine Using Tries

A practical guide to prefix trees in Python, with code you can run and extend.

You type two letters into a search bar and, before you have even decided on the third, a list of suggestions is already waiting. It feels like magic, but it is really a data structure doing its job. Behind many autocomplete boxes is a system that can answer a simple question quickly: “What starts with these letters?”
If you have ever tried to build this with a database query or a loop over a list, you may have noticed the problem: it works well with a small list and becomes less attractive as the number of words grows. A Trie, also called a prefix tree, is a data structure designed specifically for prefix-based lookups.
In this post, we will see why the obvious approach can become slow, how a Trie works, and how to build a simple autocomplete engine in Python from scratch.

Why the obvious approach gets slow

Imagine an online shop with 100,000 product names. A customer types "cat". A simple solution is to check every product and keep the names that start with "cat". In Python, that could be a loop using starts with; in SQL, it could be a prefix query such as WHERE name LIKE 'cat%'.

With N words, you may perform up to N comparisons for every keystroke. As the catalogue grows, the search box has more work to do.

A database index can make prefix queries fast, and for many applications that is enough. But when you want a lightweight in-memory autocomplete engine that responds on every keystroke, a Trie is a useful alternative because it stores shared prefixes together.

What is a Trie?

A Trie (the name comes from "retrieval", and is usually pronounced "try") is a tree where each step down the tree adds one character. Instead of storing each word as one separate object, words are represented as paths from the root.

Words with the same beginning share the same path. This means a prefix is represented once, and the node you reach tells you exactly which prefix you have matched.

For example, here is how cat, to, and top can be stored. A star (*) marks a node where a complete word ends:

text
(root)
/ \
c t
| |
a o*
| |
t* p*

Reading down the left branch gives cat. On the right, to is a complete word, while top extends it. The star is what tells us that a node represents a complete stored word.

Why is it fast?

To find words beginning with c, we do not scan the entire dictionary. We start at the root, follow the c branch, and immediately reach the part of the tree containing that prefix.

Finding the prefix takes O(L) time, where L is the length of the prefix. However, collecting the suggestions underneath that prefix still depends on how many matching words there are.

Building a Trie in Python

python
class TrieNode:
def init(self):
self.children = {}
self.is_end_of_word = False

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

def insert(self, word: str) -> None:
    node = self.root
    for char in word:
        if char not in node.children:
            node.children[char] = TrieNode()
        node = node.children[char]
    node.is_end_of_word = True

def search_prefix(self, prefix: str) -> list:
    node = self.root
    for char in prefix:
        if char not in node.children:
            return []
        node = node.children[char]

    results = []
    self._collect(node, prefix, results)
    return results

def _collect(self, node: TrieNode, word: str, results: list) -> None:
    if node.is_end_of_word:
        results.append(word)

    for char, child in node.children.items():
        self._collect(child, word + char, results)

if name == "main":
engine = Trie()
words = ["cat", "car", "cart", "dog", "dodge", "deer", "testing"]

for word in words:
    engine.insert(word)

user_input = "ca"
suggestions = engine.search_prefix(user_input)

print(f"User typed: '{user_input}'")
print(f"Suggestions: {suggestions}")

Output:

text
User typed: 'ca'
Suggestions: ['cat', 'car', 'cart']

How the code works

Inserting a word

insert() walks through the word one character at a time. If a character branch does not exist, it creates a new node. When the last character is reached, is_end_of_word is set to True.

Searching by prefix

search_prefix() first follows the typed prefix. If a character is missing, no stored word starts with that prefix. It then uses _collect() to traverse the matching subtree and gather complete words.

Time and space complexity

Operation	Complexity	Explanation
Insert a word	O(L)	L is the length of the word.
Check a prefix	O(L)	Depends on the prefix length.
Get suggestions	O(L + M)	M is the number of visited nodes while collecting matches.
Memory	O(total characters)	Shared prefixes reduce repeated storage.

Taking it to production

• Frequency weights: rank popular suggestions higher.
• Top-k caching: store the best few completions at each node.
• Radix trees: compress chains of single-child nodes.
• Input normalization and fuzzy matching: handle case differences and typing mistakes.

When a Trie is not the right tool

If the list is tiny, a normal list with startswith() may be simpler. For full-text search, typo tolerance, and relevance ranking across large documents, a dedicated search engine may be a better fit.

Final takeaway

A Trie changes autocomplete from “scan everything” into “follow the letters.” The core idea is small, but the same prefix-tree concept can support search boxes, spell checkers, keyboard suggestions, and other prefix-based features.

A good next exercise is to add a frequency counter and return only the top five suggestions.

Suggested tags: Python, Data Structures, Algorithms, Trie, Autocomplete, Programming