Trie (prefix tree) explained: how it works, code and complexity

What problem a trie solves

A hash set answers "is this exact word stored?" quickly, but it cannot answer "which stored words start with pre?" without checking every word. A sorted list can answer prefix queries with binary search, but inserts are slow. A trie is organized by prefixes, so prefix questions are its natural strength: autocomplete in a search box, word games, spell checking, and longest-prefix matching for network routes.

The idea in plain words

Think of a phone contact list that you narrow down one letter at a time. Typing c shows everyone starting with c, typing ca narrows the list, and so on. A trie stores the words in exactly that shape. The root is the empty prefix. Each node has a map from the next character to a child node, plus an end-of-word flag, because a word such as car can be both a complete word and a prefix of cart.

Worked example: inserting car, cart, cat and dog

The four words have 13 letters in total but need only 8 nodes below the root (c, a, r, t, t, d, o, g), because car, cart and cat share ca. Searching for ca walks two nodes and succeeds as a prefix, but ca is not a word because its node is not marked as an end. Searching for cow fails at the second step: node c has no child o.

Python implementation

Each node holds a dict of children, which handles any alphabet including Unicode. The starts_with method collects every word below a prefix, which is the core of autocomplete.

class TrieNode:
    __slots__ = ("children", "is_word")
    def __init__(self):
        self.children = {}
        self.is_word = False
class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = 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 contains(self, word):
        node = self._find(word)
        return node is not None and node.is_word
    def starts_with(self, prefix):
        node, out = self._find(prefix), []
        stack = [(node, prefix)] if node else []
        while stack:
            node, path = stack.pop()
            if node.is_word:
                out.append(path)
            for ch, child in node.children.items():
                stack.append((child, path + ch))
        return sorted(out)

t = Trie()
for w in ["car", "cart", "cat", "dog"]:
    t.insert(w)
print(t.contains("car"), t.contains("ca"))  # True False
print(t.starts_with("ca"))                  # ['car', 'cart', 'cat']
print(t.starts_with("x"))                   # []

starts_with sorts its output for a stable order. A real autocomplete would also stop after the first few results and rank them, for example by stored popularity counts.

Time and space complexity

The time does not depend on the number of words n, which is the main advantage over a balanced tree of strings (O(m log n) comparisons). The cost is memory: each node is a separate object with its own dictionary, so a trie can use many times more memory than the raw strings.

Variants and common mistakes

• Array children: use a fixed array of 26 slots for lowercase English. Faster than a dict, but wasteful for sparse or large alphabets.
• Compressed trie (radix tree, Patricia trie): merges chains of single-child nodes into one edge labeled with a string, which saves a lot of memory. Radix trees are used for IP routing tables and in some HTTP routers.
• Ternary search tree: each node has three children (less, equal, greater), which uses less memory than a wide array.
• Counting trie: store a counter in each node to answer "how many words start with this prefix?" in O(m).
• Bitwise trie: store numbers bit by bit to solve maximum-XOR problems.

When to use a trie and typical interview problems

Use a trie when you need prefix queries, longest-prefix matching or ordered iteration over many strings with shared prefixes. Use a set or dict when you only need exact-match lookups: it is simpler and uses less memory in Python. For small, static word lists, a sorted list with the bisect module also answers prefix queries well.

Typical problems: implement a trie (insert, search, starts-with), word search in a grid with many target words, replace words with their shortest root, longest common prefix, design a search autocomplete system, and maximum XOR of two numbers using a bitwise trie.