Trie Data Structure for Fast String Search: Autocomplete and Prefix Matching in Python

A Hash Map Can’t Do This

Here’s a question that sounds trivial until you actually try to solve it efficiently: given a dictionary of 100,000 words, return all words that start with “pre”. With a hash map, you’d iterate through every single key. That’s $O(n)$ where $n$ is the total number of words. With a trie, it’s $O(m + k)$ — where $m$ is the length of the prefix and $k$ is the number of matches. On a dataset of 100k English words, searching for all words starting with “pre” touches maybe 200 nodes instead of 100,000 entries.

That difference matters.

The Mental Model: A Tree Where Every Edge Is a Character

Forget the formal definition for a moment. Picture typing into a search bar. You type “p”, and the system narrows down to all words starting with “p”. Then “pr” — fewer candidates. Then “pre” — fewer still. A trie is literally this narrowing process encoded as a tree. Each node represents a prefix, and children branch out by the next character. The word “prefix” and “predict” share the path p → r → e, then diverge at the fourth character.

The name “trie” comes from retrieval, though most people pronounce it “try” to avoid confusion with “tree.” Edward Fredkin gets credit for the name (circa 1960), though the idea showed up earlier in work by Axel Thue and others.

A node in a trie doesn’t store the full string. It stores just enough information to know: (1) what children exist, and (2) whether this node marks the end of a valid word. That’s it. The string itself is implicit in the path you took to get there.

The Brute Force Baseline

Before building a trie, consider the naive approach for autocomplete — because in an interview, you should always start here.

def autocomplete_naive(words: list[str], prefix: str) -> list[str]:
    return [w for w in words if w.startswith(prefix)]

This is $O(n \cdot m)$ where $n$ is the number of words and $m$ is the average word length (since startswith itself is $O(m)$). For a one-off query, this is fine. For repeated queries against the same dataset — like powering a search bar that fires on every keystroke — it’s wasteful. You’re re-scanning the entire list every time the user types a character.

Sorting the list and using binary search is a middle ground. You can find the range of matching prefixes in $O(m \log n)$ with bisect_left and bisect_right. But a trie beats it for the interactive case because moving from prefix “pr” to “pre” is a single node traversal, not a fresh binary search.

Building the Trie: Node by Node

Here’s a clean implementation. I’m using a dictionary for children rather than a fixed-size array of 26 slots — the array approach wastes memory when the alphabet is large (think Unicode) or when the trie is sparse.

class TrieNode:
    __slots__ = ('children', 'is_end', 'count')

    def __init__(self):
        self.children: dict[str, 'TrieNode'] = {}
        self.is_end = False
        self.count = 0  # number of words passing through this node


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

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
            node.count += 1
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self._find_node(word)
        return node is not None and node.is_end

    def starts_with(self, prefix: str) -> bool:
        return self._find_node(prefix) is not None

    def count_prefix(self, prefix: str) -> int:
        """How many inserted words have this prefix?"""
        node = self._find_node(prefix)
        return node.count if node else 0

    def _find_node(self, prefix: str) -> TrieNode | None:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

    def autocomplete(self, prefix: str, limit: int = 10) -> list[str]:
        node = self._find_node(prefix)
        if node is None:
            return []

        results = []

        def dfs(current: TrieNode, path: list[str]):
            if len(results) >= limit:
                return
            if current.is_end:
                results.append(prefix + ''.join(path))
            for ch in sorted(current.children):
                path.append(ch)
                dfs(current.children[ch], path)
                path.pop()

        dfs(node, [])
        return results

The __slots__ on TrieNode isn’t just style — it genuinely reduces memory per node. Without it, every node carries a __dict__, which on CPython 3.11 adds roughly 100+ bytes of overhead. With __slots__, each node is much leaner. When you’re storing 100k words with an average of, say, 8 characters, that’s potentially hundreds of thousands of nodes.

The count field tracks how many words pass through each node. This is a small addition that unlocks a common interview question: “how many words in the dictionary start with this prefix?” Without it, you’d need a DFS from the prefix node to count — turning an $O(m)$ query into $O(k)$ where $k$ could be large.

Walking Through an Example

Let’s insert three words: “app”, “apple”, “api”.

root
 └── 'a' (count=3)
      └── 'p' (count=3)
           ├── 'p' (count=2)
           │    └── (is_end=True, "app")
           │         └── 'l' (count=1)
           │              └── 'e' (count=1, is_end=True, "apple")
           └── 'i' (count=1, is_end=True, "api")

Searching for “ap” — traverse root → ‘a’ → ‘p’. Node exists, is_end is False. So “ap” is a valid prefix but not a word. count_prefix("ap") returns 3.

Searching for “app” — traverse root → ‘a’ → ‘p’ → ‘p’. Node exists, is_end is True. It’s both a valid prefix and a complete word.

Searching for “ax” — traverse root → ‘a’, then look for ‘x’ in children. Not found. Return None.

Every search operation is $O(m)$ where $m$ is the length of the query string. It doesn’t matter if the trie contains 10 words or 10 million — the lookup time depends only on the query length.

Autocomplete: Collecting All Words Under a Prefix

This is where tries actually shine in practice. Given a prefix, find all words that start with it.

The autocomplete method defined in the Trie class above uses DFS to collect all words under a given prefix node. Here’s the method again for clarity:

def autocomplete(self, prefix: str, limit: int = 10) -> list[str]:
    node = self._find_node(prefix)
    if node is None:
        return []

    results = []

    def dfs(current: TrieNode, path: list[str]):
        if len(results) >= limit:
            return
        if current.is_end:
            results.append(prefix + ''.join(path))
        for ch in sorted(current.children):  # sorted for lexicographic order
            path.append(ch)
            dfs(current.children[ch], path)
            path.pop()

    dfs(node, [])
    return results

The limit parameter is non-negotiable in production. Without it, searching for “a” in an English dictionary returns tens of thousands of results. No autocomplete UI needs that. The sorted() call on children keys gives lexicographic ordering, which is usually what users expect.

But here’s a gotcha that bit me: using string concatenation inside the DFS (prefix + ch + ...) creates a new string at every node. Strings in Python are immutable, so each concatenation is $O(m)$. Using a list and joining at the end (like the code above) avoids quadratic behavior on deep tries. For short words it doesn’t matter, but tries can store URLs, file paths, DNA sequences — strings with thousands of characters.

Let’s see it work:

trie = Trie()
words = ["apple", "app", "application", "api", "apex", "banana", "apply", "appreciate"]
for w in words:
    trie.insert(w)

print(trie.autocomplete("app"))
# ['app', 'apple', 'application', 'apply', 'appreciate']

print(trie.autocomplete("app", limit=3))
# ['app', 'apple', 'application']

print(trie.autocomplete("xyz"))
# []

print(trie.count_prefix("app"))
# 5

The time complexity for autocomplete is $O(m + k \cdot L)$ where $m$ is the prefix length, $k$ is the number of results collected, and $L$ is the average length of the matching words (for the string joining). Space for the DFS stack is $O(L_{\max})$, the length of the longest word.

The Delete Operation Nobody Remembers

Insertion and search get all the attention, but deletion is where the bugs live. You can’t just set is_end = False and walk away — that leaves orphan nodes wasting memory. And you can’t aggressively prune nodes that are shared with other words.

def delete(self, word: str) -> bool:
    """Returns True if word was found and deleted."""
    def _delete(node: TrieNode, word: str, depth: int) -> bool:
        if depth == len(word):
            if not node.is_end:
                return False  # word doesn't exist
            node.is_end = False
            node.count -= 1
            return len(node.children) == 0  # safe to prune if no children

        ch = word[depth]
        if ch not in node.children:
            return False

        should_delete_child = _delete(node.children[ch], word, depth + 1)

        if should_delete_child:
            del node.children[ch]

        node.count -= 1
        return not node.is_end and len(node.children) == 0

    # Check existence first to avoid decrementing counts for non-existent words
    if not self.search(word):
        return False
    _delete(self.root, word, 0)
    return True

I’ll be honest — getting the count decrement right during deletion is fiddly. The version above does a pre-check with search() to avoid corrupting counts when deleting a word that doesn’t exist. The inner _delete function assumes the word is present, so it decrements count at every node along the path and prunes childless non-terminal nodes on the way back up. There’s probably a cleaner way to handle this with a single pass, but in an interview, correctness beats elegance. My best guess is that most production trie implementations skip deletion entirely and just do periodic rebuilds.

LeetCode Problem #208: Implement Trie

This is the canonical trie problem and it’s almost exactly what we’ve built. LeetCode 208 asks for insert, search, and startsWith. Here’s the submission-ready version:

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node['$'] = True  # end-of-word marker

    def search(self, word: str) -> bool:
        node = self._find(word)
        return node is not None and '$' in node

    def startsWith(self, prefix: str) -> bool:
        return self._find(prefix) is not None

    def _find(self, prefix: str):
        node = self.root
        for ch in prefix:
            if ch not in node:
                return None
            node = node[ch]
        return node

Wait, where did the TrieNode class go? This version uses nested dictionaries instead of explicit node objects. Each dict represents a node, keys are characters (children), and '$' is the end-of-word sentinel. It’s more compact to write in an interview and, surprisingly, often faster in Python because dict lookups are heavily optimized in CPython.

The tradeoff: you lose the ability to attach metadata (like count) cleanly. For LeetCode, the dict approach is fine. For anything more complex, go with explicit nodes.

The Interview Problem That Catches People: Word Search II (LeetCode 212)

This is the hard-tier problem where tries prove their worth. Given an $m \times n$ board of characters and a list of words, find all words that can be formed by sequentially adjacent cells (up, down, left, right), where each cell is used at most once per word.

The brute force approach: run DFS from every cell for every word. If you have $W$ words and the board is $m \times n$, that’s $O(W \cdot m \cdot n \cdot 4^L)$ where $L$ is max word length. With $W = 30000$ (the constraint), this times out.

The trie insight: build a trie from the word list, then run DFS on the board once. At each cell, you’re simultaneously walking the trie and the board. If the current path doesn’t match any prefix in the trie, prune immediately.

def findWords(board: list[list[str]], words: list[str]) -> list[str]:
    # Build trie from word list
    root = {}
    for word in words:
        node = root
        for ch in word:
            node = node.setdefault(ch, {})
        node['#'] = word  # store the full word at the terminal node

    rows, cols = len(board), len(board[0])
    found = []

    def backtrack(r: int, c: int, parent: dict):
        ch = board[r][c]
        if ch not in parent:
            return

        node = parent[ch]

        if '#' in node:
            found.append(node['#'])
            del node['#']  # avoid duplicates — remove word after finding it

        board[r][c] = '!'  # mark visited

        for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != '!':
                backtrack(nr, nc, node)

        board[r][c] = ch  # restore

        # Pruning: if node has no children left, remove it from parent
        if not node:
            del parent[ch]

    for r in range(rows):
        for c in range(cols):
            backtrack(r, c, root)

    return found

Two subtle optimizations here that interviewers love to see:

1. Storing the full word at the terminal node (node['#'] = word). This avoids rebuilding the word from the path during DFS. Minor optimization, but it simplifies the code significantly.

2. Progressive trie pruning (if not node: del parent[ch]). After finding a word, if a branch has no more words to find, remove it entirely. This makes subsequent searches faster. On large word lists, this optimization can mean the difference between TLE and acceptance. The time complexity drops to something like $O(m \cdot n \cdot 4 \cdot 3^{L-1})$ in the worst case (the first step has 4 directions, subsequent steps have 3 since you can’t go back), but the trie pruning makes the average case much better.

And here’s an edge case I almost forgot: what if the board contains characters that aren’t in any word? The trie handles this naturally — ch not in parent catches it at the first character. But what about duplicate words in the input list? The del node['#'] line handles deduplication. Without it, you’d get the same word multiple times if it can be formed via different paths.

Memory: The Elephant in the Room

Tries use a lot of memory. Each node in the dictionary-based implementation carries the overhead of a Python dict object (roughly 200+ bytes empty on CPython 3.11). For an English dictionary of 250,000 words with an average length of 8 characters, you might have around 800,000 nodes. That’s easily 150-200MB in Python.

Compare that to just storing the words in a sorted list: 250,000 strings of average length 8 is maybe 20MB. A factor of 10x more memory for the trie.

The formal space complexity is $O(N \cdot L \cdot |\Sigma|)$ where $N$ is the number of words, $L$ is average word length, and $|\Sigma|$ is alphabet size — though with dict-based children, you only pay for characters that actually exist, bringing it closer to $O(\text{total characters across all words})$.

For interviews, this rarely matters. But it’s worth mentioning if asked about tradeoffs.

Where $m$ = query length, $n$ = number of words, $k$ = number of matches.

Compressed Tries and Practical Variants

What if your trie has long chains of single-child nodes? The word “internationalization” creates 20 nodes where most have exactly one child. A compressed trie (also called a radix tree or Patricia trie) merges these chains into single edges labeled with strings instead of characters. This reduces node count dramatically.

Python’s standard library doesn’t include a trie, but the pygtrie package provides a solid implementation. For production autocomplete, most systems don’t use plain tries at all — they use ternary search trees, DAWGs (Directed Acyclic Word Graphs), or just Elasticsearch with prefix queries.

But why do interviewers keep asking about the plain trie? Because it tests whether you can implement a tree structure from scratch, handle recursive traversal, and reason about time-space tradeoffs. The data structure itself is less important than the thinking it demonstrates.

A Quick Benchmark

I wanted to see how the trie actually performs against the naive approach. Using the words_alpha.txt dataset (~370,000 English words, easily found on GitHub):

import time

# Assume `words` is a list of ~370k English words loaded from file
trie = Trie()
for w in words:
    trie.insert(w)

prefixes_to_test = ["pre", "anti", "z", "th", "xyz"]

# Trie approach
start = time.perf_counter()
for _ in range(1000):
    for p in prefixes_to_test:
        trie.starts_with(p)
print(f"Trie: {time.perf_counter() - start:.4f}s for 5000 lookups")

# Naive approach
start = time.perf_counter()
for _ in range(1000):
    for p in prefixes_to_test:
        any(w.startswith(p) for w in words)
print(f"Naive: {time.perf_counter() - start:.4f}s for 5000 lookups")

On my machine (Python 3.11, M1 MacBook Air), the trie finished 5000 starts_with lookups in about 0.003s. The naive approach took around 2.1s. That’s roughly a 700x speedup for prefix existence checking. The gap narrows if you’re collecting all matches (since you still need to traverse the subtree), but for the common case of “does any word start with X” — which is what drives early pruning in problems like Word Search II — the trie is overwhelmingly faster.

I’m not entirely sure how much of that naive approach time is Python loop overhead versus actual comparison work. A numpy-based approach with vectorized string operations might close the gap somewhat, but you’d lose the incremental prefix-narrowing property.

The Gotchas That Matter in Interviews

Empty string insertion: what happens if someone calls trie.insert("")? With the implementation above, it sets root.is_end = True. Depending on the problem, this might be valid or might need a guard. I’d add if not word: return at the top of insert unless the problem explicitly allows empty strings.

Note that there’s a subtlety with the count field here: since count is incremented inside the for ch in word loop, root.count is never incremented during any insertion. This means count_prefix("") always returns 0, even if the trie contains words. If you need a total word count, maintain a separate counter or increment root.count before the loop.

Case sensitivity: “Apple” and “apple” are different paths in the trie. If the problem says “lowercase English letters only” (most LeetCode problems do), you’re fine. Otherwise, normalize with .lower() before insertion and search.

Unicode: if you’re dealing with non-ASCII text, each “character” might be a multi-byte sequence. Python 3 handles this correctly (strings are sequences of Unicode code points), but your trie’s branching factor explodes. For CJK text, each node could have thousands of children.

And one more thing — don’t confuse a trie with a suffix tree. A suffix tree stores all suffixes of a string and enables substring search in $O(m)$ time (not just prefix search). Suffix trees are built using Ukkonen’s algorithm (Ukkonen, 1995) in $O(n)$ time, which is brilliant but significantly more complex. If an interviewer asks for substring matching, a trie alone won’t cut it.

When Not to Use a Trie

If you only need exact-match lookups, a hash set is simpler and faster. If your dataset is small (under a few thousand entries), the naive startswith scan is perfectly fine — the constant factors of maintaining a trie aren’t worth it.

Tries make sense when you need prefix operations on a large, relatively static dataset: autocomplete, spell checkers, IP routing tables (using bit-level tries), T9 phone input prediction. If the dataset changes frequently and you need deletion, consider a balanced BST of strings or a hash map with sorted keys instead.

For coding interviews specifically, reach for a trie when you see these signals: multiple string searches against the same dictionary, prefix matching, “find all words that…” queries, or grid-based word search problems. The combination of Topological Sort for DAG problems, Union-Find for connectivity, and tries for string problems covers a surprisingly large chunk of the “hard” category.

Use the nested-dict trick for fast interview coding. Switch to explicit TrieNode classes when you need metadata like counts or frequency rankings. Skip the trie entirely if a hash set solves the problem — don’t over-engineer.

One thing I haven’t explored deeply enough: how modern trie variants like the HAT-trie (Askitis and Sinha, 2007) combine cache-friendly array layouts with trie logic to get both speed and memory efficiency. The theory looks promising, but I haven’t benchmarked a Python implementation. That’s on my list.