Tries in Python: The Data Structure Behind Autocomplete

Type car into a search box and the suggestions appear before you have finished the word. The interesting part is not that they appear quickly — it is that they would appear just as quickly if the dictionary behind the box held ten words or ten million. That is not a caching trick. It is a data structure whose lookup cost genuinely does not depend on how much it is storing.

A trie is a tree keyed by character. Pronounce it "try"; the name comes from retrieval. The path from the root down to a node spells a prefix, and a single boolean on each node says whether that prefix is also a complete word. No node holds a string. The keys live in the paths, which is the whole idea and the source of every property that follows.

That one decision buys something a hash table cannot do at any price: given a prefix, produce every key that starts with it, without ever looking at a key that does not. Below you will build a trie from scratch — insert, search, starts_with, a collector for every word under a prefix, and delete, which is the one people get wrong — count what each operation really costs, and see the memory bill it hands you in return.

The idea

Start with an empty root node. It represents the empty prefix. To store a word, walk down from the root one character at a time: if a child for that character already exists, step into it; if it does not, create it. When the word runs out, set a flag on the node you landed on saying "a word ends here".

That is insertion, and it is the entire structure. Searching is the same walk without the creating: follow the characters, and if you ever ask for a child that is not there, the word is not stored.

Take five words: cat, car, card, do, dog. They spell out this tree.

Two details in that picture do all the teaching.

The flag is not optional. The node reached by the path c then a exists — three of the five words go through it — but ca was never inserted as a word. Without a per-node boolean, all a search can ask is "does this path exist", so c and ca come back as stored words even though only cat, car and card put them there. That is the single most common trie bug.

A word can end at a node that has children. do is a stored word, and it is also the first two characters of dog. So the node for do has its flag set and a child g. The same happens at car, which is a word and the parent of card. Ends and prefixes are independent facts about a node.

Count the nodes: eight, plus the root. The five words contain fifteen characters between them, so the shared prefixes have already saved seven nodes. That saving is what makes a trie viable on real vocabulary, where thousands of words start with re and every one of them shares the same two nodes.

Watching it work

Insert the five words in order and watch the tree grow. Every step is either "reuse an existing child" or "create one".

Insert cat. The root has no children at all, so all three nodes are new: c, then a, then t. Set the flag on t. The trie now holds one word in three nodes.

Insert car. The root has a c — reuse it. That c has an a — reuse it. That a has no r, so create one and flag it. One new node bought a second word, because ca was already paid for.

Insert card. Walk c, a, r, all of which exist. The r node has no d, so create it and flag it. Note what did not happen: the flag on r stayed set. car is still a word; it simply has a longer word growing out of it now.

Insert do. The root has no d, so this word shares nothing. Create d, create o, flag o. The trie now has two top-level branches.

Insert dog. Reuse d, reuse o, create g, flag g. The o node now carries a flag and a child, exactly like r did.

Now query it. Each query below is the same downward walk; only what happens at the end differs.

• search("car") — three child lookups reach the r node, whose flag is set. True.
• search("ca") — two lookups reach a node that exists, whose flag is not set. False. This is the case the flag exists for.
• search("cards") — four lookups reach d, the fifth asks d for a child s and gets nothing. False, after five steps, whatever else the trie contains.
• starts_with("ca") — the same two lookups as search("ca"), but the answer is just "did the path survive". True.
• starts_with("cab") — the a node has children t and r, no b. False.

The interesting one is collecting every word under a prefix. For ca: descend two steps to the ca node, then walk everything below it, emitting a word each time you pass a flagged node.

Visiting the ca subtree in alphabetical order gives car (flagged), then card below it (flagged), then cat (flagged) — the list car, card, cat. The d, o, g branch was never read, never compared against, never touched. That is the property no hash table can imitate: a hash deliberately scatters car and card to unrelated buckets, so the only way to answer a prefix question with a set is to test all n words one by one.

The code

Here is the complete structure. No method in it runs to more than a few lines, because the tree shape is doing the work rather than the code.

class TrieNode:
    """One character position in the trie."""

    __slots__ = ("children", "is_end")

    def __init__(self) -> None:
        # Keyed by the single character that leads to each child.
        self.children: dict[str, "TrieNode"] = {}
        # True only when a complete inserted word stops here.
        self.is_end: bool = False


class Trie:
    """A prefix tree over strings.

    Every operation costs O(m) in the length of the key handed to it, and
    nothing in this class ever looks at how many words are already stored.
    """

    def __init__(self) -> None:
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        """Add a word, creating only the nodes its path does not already have."""
        node = self.root
        for char in word:
            # setdefault is the whole trick: reuse the child when this prefix
            # has been seen before, create it exactly once when it has not.
            node = node.children.setdefault(char, TrieNode())
        node.is_end = True

    def _descend(self, prefix: str) -> "TrieNode | None":
        """Follow prefix down from the root, or None if the path runs out."""
        node = self.root
        for char in prefix:
            child = node.children.get(char)
            if child is None:
                return None
            node = child
        return node

    def search(self, word: str) -> bool:
        """True only for a word that was inserted, not one merely spelled en route."""
        node = self._descend(word)
        return node is not None and node.is_end

    def starts_with(self, prefix: str) -> bool:
        """True if at least one stored word begins with prefix."""
        return self._descend(prefix) is not None

    def words_with_prefix(self, prefix: str) -> list:
        """Every stored word beginning with prefix, in alphabetical order."""
        start = self._descend(prefix)
        if start is None:
            return []
        found: list = []
        self._collect(start, prefix, found)
        return found

    def _collect(self, node: "TrieNode", path: str, found: list) -> None:
        # Depth-first walk of one subtree. Sorting the children is what makes
        # the output alphabetical; drop it and you get insertion order.
        if node.is_end:
            found.append(path)
        for char in sorted(node.children):
            self._collect(node.children[char], path + char, found)


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

print(trie.search("car"), trie.search("ca"), trie.search("cards"))
print(trie.starts_with("ca"), trie.starts_with("cab"))
print(trie.words_with_prefix("ca"))
print(trie.words_with_prefix("do"))
print(trie.words_with_prefix("z"))

True False False
True False
['car', 'card', 'cat']
['do', 'dog']
[]

Every line matches the walkthrough above, including the two that catch people out: search("ca") is False because the flag is not set, and words_with_prefix("do") returns do itself as well as dog, because a prefix of a stored word can be a stored word.

How the code maps to the idea

TrieNode holds two things and no key. A dict from one character to the next node, and a boolean. __slots__ is there because a real dictionary produces hundreds of thousands of these objects, and slots removes the per-instance __dict__ that would otherwise sit on every one of them.

insert is a loop over characters with setdefault doing the branching. node.children.setdefault(char, TrieNode()) means "give me the child for this character, creating it if it is missing". One line covers both the reuse case and the create case. It is worth knowing that the TrieNode() argument is built on every iteration whether it is needed or not — Python evaluates arguments before the call — so on a hot insert path you would write the explicit if char not in node.children version instead.

_descend is the shared engine. search, starts_with and words_with_prefix all begin by walking the same path; they differ only in what they do when the walk ends. starts_with asks "did I get a node". search asks "did I get a node, and is its flag set". That one extra check is the entire difference between the two operations, and it is why they cost the same.

_collect is a depth-first traversal of one subtree, exactly as covered in depth-first search, carrying the string spelled so far down the recursion. Because it visits sorted(node.children) at each node, the words come out in alphabetical order. That is not quite free — it sorts at every node — but what it sorts is one node's children, at most an alphabet's worth of single characters, never n whole strings. A hash table stores keys in an order derived from their hashes and can only produce sorted output by sorting all of them.

The edge cases fall out of the loops. An empty prefix makes _descend return the root immediately, so starts_with("") is always True. That is the right answer for a trie with anything in it and the wrong one for an empty trie, where nothing is stored and the honest answer is False; if that distinction matters, keep a word count and check it first. insert("") sets the flag on the root, and search("") then returns True. A trie with no words has a root with an empty children dict, and every get returns None on the first character.

Seen from the side, the whole structure is just nested dictionaries — one dict per prefix, mapping the next character to the next dict.

Deleting a word

Delete is the operation that separates a working trie from a broken one, because a node is shared property. Removing the path for card would take car and cat with it. The rule is narrow: clear the flag, then delete a node only if it now leads nowhere at all.

Three cases, and the code must handle all three:

• The word is not there. Either the path runs out partway, or it completes but lands on a node with no flag — that is delete("ca"), which must change nothing and report failure.
• The word is a prefix of a longer word. delete("do") when dog is stored clears the flag on the o node and stops. The node itself must survive, because dog still needs to pass through it.
• The word is a dead end. delete("card") clears the flag on d, which now has no children and no flag, so nothing can ever reach it again — unlink it from its parent. Then check the parent under the same rule, and keep going up until you hit a node that has another child or is a word itself.

Recursion gives you the walk back up the path for nothing, which is why the delete below recurses when the other operations loop.

class TrieWithDelete(Trie):
    """A trie that also removes words and prunes what they leave behind."""

    def delete(self, word: str) -> bool:
        """Remove word if it is stored. True when something was actually removed."""
        return self._delete(self.root, word, 0)

    def _delete(self, node: "TrieNode", word: str, depth: int) -> bool:
        if depth == len(word):
            if not node.is_end:
                return False  # the path exists, but no word ends here
            node.is_end = False
            return True

        char = word[depth]
        child = node.children.get(char)
        if child is None:
            return False  # the word was never inserted

        removed = self._delete(child, word, depth + 1)
        # Prune on the way back up. A child with no children of its own and no
        # word ending on it cannot be reached by any query, so it can go.
        if removed and not child.children and not child.is_end:
            del node.children[char]
        return removed


trie = TrieWithDelete()
for word in ["cat", "car", "card", "do", "dog"]:
    trie.insert(word)

print(trie.delete("card"), trie.words_with_prefix("ca"))
print(trie.delete("do"), trie.words_with_prefix("do"))
print(trie.delete("cab"), trie.delete("ca"))
print(trie.search("cat"), trie.starts_with("ca"))

True ['car', 'cat']
True ['dog']
False False
True True

Line one removed card and pruned its d node, leaving car and cat untouched. Line two removed the word do but kept its node, so dog still resolves. Line three shows the two ways a delete fails: a path that does not exist, and a path that exists but is only a prefix. Line four confirms the neighbours survived.

The second half of the prune condition is the load-bearing part. After delete("card") unlinks the d node, its parent r has no children left — and r is the word car. Prune on "no children" alone and deleting card silently deletes car too. The not child.is_end test is what stops that, and it only ever fires when one stored word is a prefix of another, which is exactly the case a quick test suite misses.

Complexity

Write m for the length of the key you pass in and n for the number of words already stored. The point of this section is that n does not appear.

Insert: O(m). The loop runs once per character. Each iteration does one dict setdefault on a one-character key. Hashing a one-character string is constant work. A CPython dict lookup is O(1) on average and O(k) in the worst case, where k is the number of keys that collide — but k here is one node's child count, capped by the alphabet, so even the pathological case is a constant factor and not a term that grows with m or n. There are exactly m iterations, and at most m nodes are created.

Search and starts_with: O(m). The same m dict lookups, then one boolean check. Both stop the moment a character is missing, so search("cards") on the five-word trie costs five lookups and no more. No comparison is ever made against a stored word, because there are no stored words to compare against — only paths.

Collecting a prefix: O(m + s). The descent is m lookups. Then the collector visits every node of the subtree exactly once; call that s nodes. Nothing outside the subtree is touched, so if 4 of your 200,000 words start with zyg, the collection reads a handful of nodes, not 200,000 strings. There is one cost hiding in the recursion: path + char builds a fresh string at every node, copying the whole prefix each time, so the character-copying work is O(s × longest match) rather than O(total output). For autocomplete-length words that is invisible; for long keys, pass a list of characters down and "".join it at each flagged node.

Delete: O(m). m levels down, m levels back up, constant work at each level.

Space: one node per distinct prefix. The upper bound is 1 + the total number of characters across all words, hit only when no two words share a first character. Every shared prefix pushes you below it.

Auxiliary space: O(m). The three loops use none, but the two recursive methods do. delete holds one frame per character of the key, and _collect holds one per level of the subtree it is walking, so the peak is the longest word under the prefix. For English words that is a handful of frames. It stops being invisible at CPython's default recursion limit of 1000: a key around a thousand characters long makes delete and words_with_prefix raise RecursionError instead of returning. If your keys are DNA strings or file paths, rewrite both with an explicit stack.

Both of those last two claims are easier to measure than to trust.

def count_nodes(trie: Trie) -> int:
    """Every node in the trie, the root included."""
    total = 0
    stack = [trie.root]
    while stack:
        node = stack.pop()
        total += 1
        stack.extend(node.children.values())
    return total


sample = ["car", "card", "cardigan", "cardinal", "care", "careful",
          "cat", "catalog", "do", "dodge", "dog", "dot"]
words = Trie()
for word in sample:
    words.insert(word)

print(f"{len(sample)} words, {sum(len(w) for w in sample)} characters, "
      f"{count_nodes(words)} nodes")

12 words, 57 characters, 28 nodes

Fifty-seven characters compressed into 27 nodes plus a root, because car is stored once and reused by six words. Now the claim that matters — that a lookup does not care how much is in the trie.

from itertools import product

one_word = Trie()
one_word.insert("cardinal")

many_words = Trie()
for letters in product("abcdefghij", repeat=4):
    many_words.insert("".join(letters))
many_words.insert("cardinal")


def child_lookups(trie: Trie, word: str) -> int:
    """How many child lookups a search for word performs."""
    node, steps = trie.root, 0
    for char in word:
        steps += 1
        node = node.children.get(char)
        if node is None:
            break
    return steps


print(f"trie of 1 word:      {child_lookups(one_word, 'cardinal')} child lookups, "
      f"{count_nodes(one_word)} nodes")
print(f"trie of 10001 words: {child_lookups(many_words, 'cardinal')} child lookups, "
      f"{count_nodes(many_words)} nodes")

trie of 1 word:      8 child lookups, 9 nodes
trie of 10001 words: 8 child lookups, 11117 nodes

Eleven thousand nodes versus nine, and the search does the identical eight steps. Multiply the word count by another thousand and it is still eight.

Against a hash table

The honest comparison, because tries are often oversold here. Looking a word up in a Python set is not O(1) in the length of the word: the hash function reads every character, and a successful lookup then compares the full string character by character. A hash table is O(m) for string keys too. The trie is not asymptotically faster — it is asymptotically the same with a far worse constant, because m Python-level dict lookups and m pointer dereferences lose badly to one tight C loop over a contiguous buffer.

What changes is the set of questions you can ask.

Reach for a trie when a row below the first one is the row you care about.

The memory bill

Nodes are not free, and in Python they are expensive. Measured with sys.getsizeof on CPython 3.9, a TrieNode with __slots__ is 48 bytes, and its children dict costs 64 bytes while empty but jumps to 232 bytes the moment it holds a single child. That puts a branching node at roughly 280 bytes to store one character. The 28-node trie above works out at about 6 KB to hold 12 words whose Python strings total under 700 bytes — an order of magnitude worse. Exact figures move between interpreter versions; the ratio does not.

The standard fix is a compressed trie, also called a radix tree or PATRICIA trie: any chain of single-child nodes that are not words themselves collapses into one node holding the whole substring. In the sample above, catalog becomes a single alog edge hanging off cat instead of four separate nodes. The flag test in that rule is not optional — card has exactly one child but is also a word, so it has to survive as its own node. Applied to the 12-word sample, the rule takes 28 nodes down to 15. Real implementations go further and share suffixes as well as prefixes, turning the tree into a DAWG or a finite state transducer, which is what production autocomplete indexes actually store.

When to use it, and when not to

Use a trie when prefixes are the question. Autocomplete, command-line completion, dictionary lookups for a word game, routing tables that need the longest matching prefix, or any place you want the keys back in sorted order and also want fast membership.

There is a second reason autocomplete uses tries that gets less attention: the work is incremental. Keep the node you reached after the user typed c; when they type a, take one child step from it. Each keystroke is a single dict lookup, not a fresh walk from the root, and certainly not a fresh scan of the vocabulary. Suggestion latency stops depending on the length of what has been typed as well as on the size of the dictionary.

Do not use a trie for exact lookups. If all you ever ask is "is this key present" or "what value does this key hold", a dict or a set wins on speed and wins enormously on memory. Writing a trie for that is a straight downgrade.

Do not use a trie for a static word list that fits in memory. Sort it once and binary-search it. bisect_left finds the first word at or after the prefix; every match is contiguous from there.

from bisect import bisect_left


def prefix_matches(sorted_words: list, prefix: str) -> list:
    """Prefix search without a trie: one binary search, then walk forwards."""
    start = bisect_left(sorted_words, prefix)
    matches = []
    for word in sorted_words[start:]:
        if not word.startswith(prefix):
            break
        matches.append(word)
    return matches


print(prefix_matches(sorted(sample), "car"))
print(prefix_matches(sorted(sample), "do"))

['car', 'card', 'cardigan', 'cardinal', 'care', 'careful']
['do', 'dodge', 'dog', 'dot']

That is O(log n + k) comparisons for k matches — about 17 binary-search steps over 100,000 words — in a flat list that costs a tenth of the trie's memory. It loses when the vocabulary changes often, because every insert into a sorted list is O(n), and it cannot answer longest-prefix-match cleanly. Those two weaknesses are exactly where the trie earns its keep.

Python's standard library has no trie, so the choice at work is between the class above, a sorted list with bisect, or a third-party package. pygtrie is pure Python with a dict-like API, so it is convenient but pays the same memory bill as the class above; marisa-trie wraps a C++ library and gives you a static, heavily compressed structure, which is the one to reach for when memory is the problem.

Where it shows up in the real world

Search indexes. Lucene, and therefore Elasticsearch and OpenSearch, stores its term dictionary index as a finite state transducer — a trie compressed by sharing suffixes as well as prefixes. Its completion suggester, the thing that powers search-as-you-type, is built on the same machinery.

IP routing. A router does not look up an exact address, it looks up the longest stored prefix that matches one, which is precisely a walk down a trie remembering the last flagged node. The Linux kernel's IPv4 forwarding table lives in net/ipv4/fib_trie.c and is a level-compressed trie.

Redis Streams. Redis ships its own radix tree implementation, rax.c, and uses it to index stream entry IDs, which are ordered byte strings with heavily shared prefixes.

Multi-pattern text scanning. The Aho-Corasick algorithm builds a trie of every pattern, adds a failure link from each node to the longest proper suffix that is also a prefix, and then scans the text once for all patterns simultaneously. Antivirus signature matchers such as ClamAV use it.

T9 predictive text. On a numeric keypad each digit covers three or four letters, so a trie keyed by digit rather than letter turns 2-2-8 into cat, bat and act in three steps. The ambiguity is the point: one path ends at several words, and the structure hands back all of them to be ranked.

Fuzzy matching and spell check. Walk the trie carrying one row of the Levenshtein table per node and you can abandon whole subtrees at once. The test is the smallest number in that row — how far the prefix you are standing on is from the closest prefix of the query — because that minimum can only grow as you descend. Once it passes the budget, nothing below can match, and the whole subtree is dropped unread. Do not test against the distance to the full query instead: that number falls as you go deeper, since c is 2 edits from cat and cat is 0. That pruning is what makes dictionary-wide fuzzy search feasible.

Common mistakes

Leaving out is_end. The trie then reports every prefix as a stored word, so search("ca") returns True for a dictionary containing only cat. Fix: one boolean per node, checked at the end of search and only there.

Deleting the whole path. Removing every node on the path for card also removes car and cat, because those nodes were never card's to delete. Fix: clear the flag first, then unlink a node only when it has both no children and no flag of its own, working upwards. Test that with a word that is a prefix of another — delete("do") while dog is stored — because a delete can pass every other test and still fail that one.

Sharing one dict across every node. Writing children = {} in the class body instead of self.children = {} in __init__ gives every node the same dictionary object. The trie collapses into a single level: insert cat and that one dict holds c, a and t, so search("act") comes back True too. This is the classic Python mutable-class-attribute bug and it is quiet, because inserts still succeed. The __slots__ above happens to block it — a name cannot be both a slot and a class variable, so Python raises at class-definition time — but drop the slots and the bug is back.

Building the output string by concatenation for long keys. path + char at every node of the collector copies the prefix again and again. Harmless for words; quadratic for keys hundreds of characters long. Pass a list down and join once.

Reaching for a fixed array of 26 children. It is faster than a dict when the alphabet really is 26 letters, but it costs 26 pointers per node whether they are used or not, and it breaks the moment a name arrives with an accent. A dict adapts to Unicode without any change.

Practice

1. Add count_words() that reports how many words the trie holds, by walking it and counting flags rather than keeping a counter.
2. Add longest_prefix_of(text) returning the longest stored word that is a prefix of text — the routing-table operation — in a single downward walk.
3. Turn the trie into a map instead of a set: store a value on each flagged node and return it from a get(word) method.
4. Add wildcard_search(pattern) where . matches any single character, which needs backtracking across all children at each . position.
5. Write compress() that collapses every chain of single-child, unflagged nodes into one node holding a substring, and report how many nodes it saves on a dictionary of your choice.

Summary

A trie trades memory for a capability. It costs a Python object and a dictionary per stored character, which is roughly ten times what the raw strings need, and in exchange every operation costs the length of the key and nothing else — the same eight steps whether the trie holds one word or ten thousand. Use it when the questions are about prefixes; use a dict when they are not.

Build one once, delete included, and the structure stops being mysterious: it is a dictionary of dictionaries with a boolean stapled to each level. The reason it is worth the memory is that it stores the relationship between keys, not just the keys.

Keep reading

• Hash Tables in Python — the structure a trie is always measured against, and why it cannot answer prefix questions.
• Depth-First Search — the traversal the prefix collector runs, explained on its own.
• Binary Search Trees in Python — ordered keys without splitting them into characters.
• Big O Notation — the counting argument behind every bound above.
• The KMP Algorithm — prefix reuse in string matching, and the single-pattern ancestor of Aho-Corasick.