Tries

The problem a trie solves#

Imagine building a search box's autocomplete feature: as a user types "ca", you want to instantly suggest "cat", "car", "card", and "care" — every stored word that starts with what's been typed so far. You could scan your entire word list checking word.startswith(prefix) for every word — but that's O(n × m) (n words, each up to m characters to compare), redone on every single keystroke. A trie (pronounced "try," short for retrieval, though many people pronounce it like "tree" to avoid confusion) is a data structure purpose-built for exactly this: extremely fast prefix search, regardless of how many words are stored.

Analogy: think of a trie as an organized filing system where you file words letter by letter down a shared hallway of folders. Every word that starts with "c" shares the same first folder. Every word that starts with "ca" shares the folder after that, and so on. Looking up everything starting with "ca" means walking down exactly two folders and grabbing everything beneath — you never have to walk down the "d..." or "z..." hallways at all.

Structure: a tree of characters#

A trie is a tree where each edge represents one character, and any path from the root down to a specially-marked node spells out a stored word. Crucially, words that share a common prefix literally share the same nodes for that prefix — "cat" and "car" share the nodes for "c" and "ca", only branching apart at the third letter.

        (root)
         |
         c
         |
         a
        / \
       t   r
       |   |
      (end) (end)     <- "cat" and "car" both stored, sharing "c" -> "a"

Each node needs: a way to look up its children by the next character (a dictionary works perfectly), and a flag marking "a complete word ends here" — because without that flag, you couldn't tell the difference between "car" being a stored word versus just being a prefix of "card" that happens to pass through the same nodes.

A complete implementation#

class TrieNode:
    def __init__(self):
        self.children = {}       # maps a character -> the next TrieNode
        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()   # create the path if it doesn't exist yet
            node = node.children[char]
        node.is_end_of_word = True                  # mark the final node as a complete word

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

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

    def _walk(self, s: str):
        """Follow the trie down one character at a time; return the final
        node reached, or None if the path breaks before we get there."""
        node = self.root
        for char in s:
            if char not in node.children:
                return None
            node = node.children[char]
        return node


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

print(trie.search("car"))        # True  — "car" was inserted as a complete word
print(trie.search("ca"))         # False — "ca" was never inserted as a complete word...
print(trie.starts_with("ca"))    # True  — ...but plenty of stored words start with "ca"
print(trie.starts_with("cx"))    # False — no stored word starts this way
print(trie.search("dog"))        # True

Trace insert("car") then insert("card"): inserting "car" creates three new nodes, one per character, and marks the third ('r') as is_end_of_word = True. Inserting "card" walks 'c' → 'a' → 'r', finding all three nodes already exist (created by the previous insert) — it only needs to create one brand-new node for the 'd', and mark that as the end of a word. This sharing is the entire source of a trie's efficiency: common prefixes are stored exactly once, no matter how many words share them.

Time complexity: insert, search, and starts_with are all O(k), where k is the length of the word or prefix being processed — notably, this does not depend on how many other words are stored in the trie at all. Compare that to scanning a list of n words with startswith(), which costs O(n × k) — a trie turns "search proportional to how much data you have" into "search proportional only to how long your query is."

Real use case: autocomplete#

Building on starts_with, a genuinely useful autocomplete feature needs to go one step further: not just "does anything match this prefix," but "show me all the words that match." That means walking down to the end of the prefix, then exploring every branch beneath that point (a small DFS, reusing exactly the traversal idea from the graphs page):

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

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

    def _walk(self, s: str):
        node = self.root
        for char in s:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

    def autocomplete(self, prefix: str, limit: int = 5) -> list[str]:
        start_node = self._walk(prefix)
        if start_node is None:
            return []                      # nothing stored starts with this prefix

        results = []
        self._collect_words(start_node, prefix, results, limit)
        return results

    def _collect_words(self, node, path, results, limit):
        if len(results) >= limit:
            return
        if node.is_end_of_word:
            results.append(path)
        for char, child in node.children.items():
            if len(results) >= limit:
                return
            self._collect_words(child, path + char, results, limit)


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

print(trie.autocomplete("car"))    # ['car', 'card', 'care', 'careful']
print(trie.autocomplete("do"))     # ['dog']
print(trie.autocomplete("xyz"))    # []

This is, in essence, a simplified version of what powers real autocomplete in search engines, IDEs (suggesting variable/function names as you type), and phone keyboards — the same trie-walk-then-collect pattern, usually augmented with frequency data so the most commonly chosen completions are shown first rather than in arbitrary order.

Common mistakes#

• Forgetting the is_end_of_word flag. Without it, there's no way to distinguish a genuinely stored word from a node that merely happens to be a prefix of a longer stored word.
• Confusing search with starts_with. search("car") should only return True if "car" itself was inserted as a complete word; starts_with("car") should return True as long as any stored word begins with "car", even if "car" itself was never inserted.
• Assuming a trie always saves memory. It saves memory when words share many common prefixes (like a dictionary of English words); for a set of totally dissimilar strings with no shared prefixes, a trie can actually use more memory than simply storing the strings in a set, since it still creates a node per character.
• Reaching for a trie when a hash set would do. If all you need is "does this exact word exist?" (not prefix search), a plain set already answers that in O(1) average time with far less implementation complexity — a trie earns its keep specifically when prefix-based queries are the actual requirement.