Tries and Prefix Search

A tree of prefixes

A trie (pronounced "try") stores strings by sharing their prefixes. Each edge represents a character. Following the edges c, a, t reaches the word "cat"; the words "car" and "care" share the first two edges.

Each node needs:

• a mapping from characters to child nodes, and
• a flag saying whether a complete word ends there.

That end flag matters. If "care" exists, the path for "car" exists too, but "car" is a stored word only when its node is marked as an ending.

(root)
  └─ c
     └─ a
        ├─ r  * car
        │  └─ e  * care
        └─ t  * cat

Why use a trie?

Searching for a word of length L takes O(L), independent of how many other words are stored. Finding all completions for a prefix first costs O(P) for a prefix of length P, then time proportional to the part of the trie visited to produce results.

Tries work well for autocomplete, dictionaries, routing prefixes and filtering words by prefix. They are less attractive when memory is tight or prefix queries are rare.

Insert, search and autocomplete

Autocomplete first walks to the prefix node. A depth-first search then collects complete words below it. Visiting children in sorted character order makes the output deterministic.

class Node:
    def __init__(self):
        self.children = {}
        self.end = False


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

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, Node())
        node.end = True

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

    def autocomplete(self, prefix):
        node = self._walk(prefix)
        result = []
        if node is None:
            return result
        def collect(current, suffix):
            if current.end:
                result.append(prefix + suffix)
            for ch in sorted(current.children):
                collect(current.children[ch], suffix + ch)
        collect(node, "")
        return result

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


trie = Trie()
for word in ("car", "care", "cat", "dog"):
    trie.insert(word)
print("contains car:", str(trie.contains("car")).lower())
print("contains ca:", str(trie.contains("ca")).lower())
print("prefix ca:", ", ".join(trie.autocomplete("ca")))
print("prefix do:", ", ".join(trie.autocomplete("do")))

contains car: true
contains ca: false
prefix ca: car, care, cat
prefix do: dog

Extensions

Store a count instead of a Boolean ending flag when duplicate words matter. Store a popularity score to rank suggestions. For deletion, unset the ending flag and remove now-unused nodes while returning toward the root. For a fixed alphabet, an array of child slots can replace each map; it trades more memory for faster, simpler indexing.