Data Structures

Trie Data Structure: Fast Prefix Search and Autocomplete

A trie (pronounced "try") stores strings by branching on each character, grouping words with shared prefixes along the same path. Insert and search are O(k) where k is the string length, and prefix queries are free — you just walk as far as the prefix goes.

Published June 30, 2026

What Is a Trie?

A trie is a tree where each node represents one character in a set of strings. The root is empty. Starting from the root, each edge is labeled with a character, and a path from the root to a marked leaf spells out one complete word. Words that share a prefix share their path from the root up to the point where they diverge.

For example, storing "cat", "can", and "car" in a trie produces a shared path for "ca", which then branches into "t", "n", and "r". This shared structure is what makes prefix queries so efficient: to check whether any stored word starts with "ca", you only follow two edges from the root. If those edges exist, there is at least one word with that prefix.

The name comes from "retrieval." Tries were originally designed for efficient dictionary lookup and are distinct from binary trees, where each node holds a value rather than a character of a path.

How Does Insert Work?

To insert a word, walk from the root through the characters of the word one by one. At each character, check whether the current node already has a child for that character. If it does, follow the existing child. If it does not, create a new child node. After processing all characters, mark the final node as the end of a complete word.

The result is that inserting a word of length k takes exactly k steps, giving O(k) time. No hashing, no comparisons between whole strings — just pointer traversal through a tree of single characters.

How Does Prefix Search Work?

To check whether any word in the trie starts with a given prefix, walk the tree following the prefix characters. If at any point a required character is missing as a child of the current node, the prefix does not exist. If you successfully follow all prefix characters, the trie contains at least one word with that prefix.

To enumerate all words with a given prefix, walk to the prefix node, then perform a DFS or BFS from that node, collecting all paths that end at a word-end marker. This is the mechanism behind autocomplete: the user types a prefix, you walk to the prefix node in O(k) time, then collect suggestions from the subtree.

Python Implementation

Here is a complete trie implementation with insert, exact search, and prefix check:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = 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 = True

    def search(self, word: str) -> bool:
        """Returns True only if word exists exactly."""
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

    def starts_with(self, prefix: str) -> bool:
        """Returns True if any inserted word begins with prefix."""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

    def autocomplete(self, prefix: str) -> list:
        """Return all words that begin with prefix."""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]

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

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


# Usage
trie = Trie()
for word in ["apple", "app", "application", "apply", "apt"]:
    trie.insert(word)

print(trie.search("app"))          # True
print(trie.search("ap"))           # False (not a complete word)
print(trie.starts_with("ap"))      # True
print(trie.autocomplete("app"))    # ['app', 'apple', 'application', 'apply']

Trade-offs vs Hash Set

A hash set also supports O(1) average-case insert and lookup for whole strings. So when does a trie win?

Prefix queries: A hash set cannot answer "does any stored word start with X?" without scanning every element. A trie answers this in O(k) time.
Autocomplete and wildcard search: Enumeration of all words matching a pattern like "app*" is natural on a trie and expensive on a hash set.
Lexicographic ordering: Iterating a trie in DFS order yields words in sorted order for free.
Shared storage: If your word list has many common prefixes, a trie stores less data overall because the shared prefix nodes are not duplicated.

Hash sets win when you only need exact membership testing and your strings do not share meaningful prefixes. Hash sets also avoid the overhead of per-node dictionary allocations. For a set of 10,000 random UUIDs, a hash set will use less memory and be faster for lookup than a trie.

The children = {} dict inside each node is the main memory cost. A compact trie using arrays of 26 entries (for lowercase English letters) is faster to traverse but always allocates 26 pointers per node regardless of actual children. A hash-based children dict saves space for sparse alphabets at the cost of slightly slower traversal.