Tries: Prefix Trees for Fast Word Search

How a trie is organized

Each edge represents a character, and a path from the root spells a prefix. A terminal marker distinguishes a complete word from a prefix of a longer word: without it, searching for “app” could incorrectly succeed just because “apple” exists. Inserting a word of length L takes O(L); exact lookup and prefix lookup also take O(L), independent of the number of stored words.

The cost is memory. A separate node per possible next character can use more space than a hash set for a small vocabulary. Dictionary-based child maps save space for sparse alphabets but add per-node map overhead.

Compact Python implementation

class TrieNode:
    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 char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_word = True

    def search(self, word):
        node = self._walk(word)
        return node is not None and node.is_word

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

    def _walk(self, text):
        node = self.root
        for char in text:
            node = node.children.get(char)
            if node is None:
                return None
        return node

In production code, normalize case and Unicode consistently if words are meant to compare independent of those details. Keep that policy the same for insertion and queries.

Autocomplete, deletion, and tradeoffs

Autocomplete first walks the prefix, then explores descendants to enumerate matching words. Enumeration costs at least the number of output characters, so a trie cannot make returning a huge result set free. A popular product may also store frequency or ranking metadata to return the most useful suggestions first.

Deletion clears the terminal marker. A cleanup pass may remove nodes that are no longer on a path to any word, but only when they have no children and are not terminal. Common trie extensions include wildcard matching, bitwise tries for integer XOR queries, and compressed radix trees that combine chains of single-child nodes.