Trie in Python: Prefix Search Explained

A trie (pronounced “try”, from retrieval) is a tree that stores words letter by letter, so that words sharing a beginning share the same path. It is also called a prefix tree. It is what powers autocomplete on a phone keyboard, spell checkers, and the search suggestions that appear as you type.

This guide builds a trie in Python from scratch: insert, search and prefix check, then autocomplete and wildcard search. We also compare it with the simpler options you may already know, by counting steps instead of seconds. All the output shown is real.

The idea

Suppose we store car, cat, cart and dog. The three words starting with ca share their first two nodes, and only branch when the letters differ:

(root)
 |-- c -- a --+-- r* -- t*
 |            '-- t*
 '-- d -- o -- g*

A star marks a node where a word ends. Note that car ends in the middle of the path to cart, so the flag is needed to tell “car is a word” from “car is only the start of a longer word”. To look up a word you follow its letters from the root. If a letter is missing, the word is not there. This is a tree (see Binary Tree in Python), but a node can have many children, not just two.

Building a trie in Python

Each node stores its children in a dictionary, so any character works, not only a to z (see Python Dictionaries Explained). Inserting walks down the path, creating any missing nodes, and finally marks the last node as a word end. Searching walks the same path without creating anything:

class TrieNode:
    def __init__(self):
        self.children = {}          # letter -> TrieNode
        self.is_end = False         # does a word finish here?

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 _find(self, prefix):
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word):
        node = self._find(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._find(prefix) is not None

trie = Trie()
for word in ["car", "cat", "cart", "dog"]:
    trie.insert(word)

print(trie.search("car"))
print(trie.search("ca"))
print(trie.starts_with("ca"))
print(trie.search("cow"), trie.starts_with("do"))

Output

True
False
True
False True

The difference between search and starts_with is only the last check. "ca" is a prefix of several words, but not a word itself, so search("ca") is False and starts_with("ca") is True.

What the trie looks like inside

It helps to print the nodes as nested dictionaries. Every key is a letter, and the '*' key marks the end of a word:

def show(node):
    out = {}
    for ch, child in node.children.items():
        out[ch] = show(child)
    if node.is_end:
        out["*"] = True                 # a word ends here
    return out

trie = Trie()
for word in ["car", "cat", "cart", "dog"]:
    trie.insert(word)
print(show(trie.root))

Output

{'c': {'a': {'r': {'t': {'*': True}, '*': True}, 't': {'*': True}}}, 'd': {'o': {'g': {'*': True}}}}

Follow c, a, r. At that node there is a '*' (car is a word), and also a child t (cart). Both car and cat go through the same c and a nodes, stored only once.

Autocomplete: all words with a prefix

This is where a trie shines. Walk down to the node for the prefix, then collect every word below it with a depth-first search (see Recursion in Python Explained Simply). Visiting the children in sorted order gives the words in alphabetical order. Add these two methods to the class:

    def words_with_prefix(self, prefix):
        node = self._find(prefix)
        if node is None:
            return []
        results = []

        def collect(node, path):
            if node.is_end:
                results.append(prefix + path)
            for ch in sorted(node.children):
                collect(node.children[ch], path + ch)

        collect(node, "")
        return results

    def search_pattern(self, pattern):
        def dfs(node, i):
            if i == len(pattern):
                return node.is_end
            ch = pattern[i]
            if ch == ".":                       # a dot matches any single letter
                return any(dfs(child, i + 1) for child in node.children.values())
            child = node.children.get(ch)
            return child is not None and dfs(child, i + 1)

        return dfs(self.root, 0)

trie = Trie()
for word in ["apple", "app", "apply", "apt", "banana", "band"]:
    trie.insert(word)

print(trie.words_with_prefix("ap"))
print(trie.words_with_prefix("ban"))
print(trie.words_with_prefix("x"))
print(len(trie.words_with_prefix("")))

Output

['app', 'apple', 'apply', 'apt']
['banana', 'band']
[]
6

The results come out in alphabetical order. app comes before apple because a word is recorded as soon as the search reaches its end flag, before it goes deeper. A prefix with no matches gives an empty list, and the empty prefix returns every word.

Wildcard search

The second method above, search_pattern, supports a . that stands for “any one letter”. When it meets a dot, it tries every child. That kind of matching is not possible with a set of words:

trie = Trie()
for word in ["bad", "dad", "mad"]:
    trie.insert(word)

for pattern in ["pad", "bad", ".ad", "b..", "b."]:
    print(pattern, trie.search_pattern(pattern))

Output

pad False
bad True
.ad True
b.. True
b. False

b. is False because the words have three letters, and the pattern must match the whole word.

Why not just a list or a set?

For exact lookups a set is excellent: "cat" in words is O(1) on average (see Hash Table in Python). But it cannot answer prefix questions directly:

words = {"car", "cat", "cart", "dog"}
print("cat" in words)
print("ca" in words)
print(any(w.startswith("ca") for w in words))

Output

True
False
True

The only option with a set or list is to check every single word, which costs O(N x L) for N words. To see the difference, we store all 3,125 five-letter words made from the letters a to e, and ask for those starting with abc. Steps are counted, not seconds:

import itertools

words = ["".join(p) for p in itertools.product("abcde", repeat=5)]     # 3125 words
trie = Trie()
for w in words:
    trie.insert(w)

prefix = "abc"
in_list = [w for w in words if w.startswith(prefix)]
print("list scan: checked", len(words), "words, found", len(in_list))
print("trie     : walked", len(prefix), "nodes, then collected", len(trie.words_with_prefix(prefix)))

def count_nodes(node):
    return 1 + sum(count_nodes(child) for child in node.children.values())

print("letters in all the words:", sum(len(w) for w in words))
print("nodes in the trie       :", count_nodes(trie.root))

Output

list scan: checked 3125 words, found 25
trie     : walked 3 nodes, then collected 25
letters in all the words: 15625
nodes in the trie       : 3906

The list has to check all 3,125 words. The trie walks 3 nodes, one per letter of the prefix, and then everything below that node is already a match. The number of words that are stored does not matter to the search. The trie also stores the shared beginnings only once: 15,625 letters in the words become 3,906 nodes. (Actual memory use also depends on how heavy each node is in Python, which is a real cost of tries.)

Complexity

The trie’s cost depends on the length of the word and not on how many words are stored. The price is memory: each node is a Python object with a dictionary. For a big dictionary of words, that can be much more than a set. (See Big O Notation in Python for the notation.) Real systems reduce it with compressed tries or other structures, but the idea stays the same.

Common mistakes

• Forgetting the end flag. Without is_end, search("ca") would wrongly say True just because the path exists.
• A mutable default for the children. Writing def __init__(self, children={}) makes one dictionary shared by every node. Always create {} inside __init__.
• Mixing up prefix and word. Use search for whole words and starts_with for prefixes.
• Ignoring case. "Cat" and "cat" are different paths. Normalise with .lower() when needed.
• Using a trie for exact lookups only. A set is simpler and lighter. Use a trie when you need prefixes.
• Recursing very deep. Words are short, so the depth is rarely a problem, but a trie of very long strings could hit the recursion limit.

class BadNode:
    def __init__(self, children={}):        # one dict, shared by every node!
        self.children = children

a = BadNode()
b = BadNode()
a.children["x"] = "value"
print(b.children)
print(a.children is b.children)

Output

{'x': 'value'}
True

Try it yourself

Work out each answer first, then open the solution. The Trie class from above is assumed.

1. Store car, cat, cart, dog, cow and count the words that start with ca, c and z.

trie = Trie()
for word in ["car", "cat", "cart", "dog", "cow"]:
    trie.insert(word)

for prefix in ["ca", "c", "z"]:
    print(prefix, len(trie.words_with_prefix(prefix)))

ca 3
c 4
z 0

2. Find the longest common prefix of a list of words using a trie.

def longest_common_prefix(words):
    trie = Trie()
    for w in words:
        trie.insert(w)
    node, prefix = trie.root, ""
    while len(node.children) == 1 and not node.is_end:
        ch, node = next(iter(node.children.items()))
        prefix += ch
    return prefix

print(longest_common_prefix(["flower", "flow", "flight"]))
print(repr(longest_common_prefix(["dog", "car"])))

fl
''

3. Write suggest(trie, prefix, limit=3) that returns at most 3 completions.

def suggest(trie, prefix, limit=3):
    return trie.words_with_prefix(prefix)[:limit]

trie = Trie()
for word in ["apple", "app", "apply", "apt", "banana"]:
    trie.insert(word)
print(suggest(trie, "ap"))
print(suggest(trie, "ap", limit=2))

['app', 'apple', 'apply']
['app', 'apple']

4. Why does searching a trie take the same time whether it holds 100 words or 10 million?

Run these in our free Python compiler.

Frequently asked questions

What is a trie in Python?

A trie, or prefix tree, is a tree in which each node represents a letter and each path from the root spells a prefix. Python has no built-in trie, so you build one from a node class that holds a dictionary of children and an end-of-word flag.

What is a trie used for?

Autocomplete, spell checking, prefix search, word games, IP routing tables and dictionary lookups where matching by prefix matters.

What is the time complexity of a trie?

Insert, search and prefix check all take O(L), where L is the length of the word. It does not depend on how many words are stored.

What is the difference between a trie and a hash table?

A hash table (dict or set) finds an exact key in O(1) on average but cannot answer prefix questions without scanning everything. A trie handles prefixes and ordered listing naturally, but uses more memory.

How do I do autocomplete with a trie?

Walk down to the node that represents the typed prefix, then use depth-first search to collect all the words below it.

Is a trie better than a set of strings?

Only when you need prefix operations. For plain “is this word in the list” checks, a set is simpler and uses less memory.

Related reading

• Hash Tables in Python: Dict and Set for DSA – exact lookups in constant time.
• Binary Tree in Python: Traversals Explained – the tree basics behind a trie.
• Recursion in Python Explained Simply – how the collect step works.
• Python Dictionaries Explained With Examples – the children dictionary.