Tries — trees built for prefixes

A hash set answers "is this exact string present" in O(1). A trie answers a genuinely different question — "which strings share this prefix" — by literally structuring the tree around shared prefixes, one character per level.

Intermediate

4 min read

The question a hash set can't answer efficiently

words = {"cat", "car", "card", "care", "dog"}
"car" in words   # O(1) — a hash set answers this fine
 
# But: "give me every word starting with 'ca'" — a hash set has no way to
# do this without checking every single stored word individually

A hash set (from the hash-maps lesson) is excellent at "does this exact string exist," but it has no structural relationship between similar strings — "car" and "card" are hashed to completely unrelated positions, so finding "every word starting with ca" means scanning every stored word one by one, checking each against the prefix. A trie (pronounced "try," from retrieval) is a tree built specifically to make prefix questions fast, by literally organizing shared prefixes together as shared paths through the tree.

Each edge in a trie represents one character; walking from the root down some path spells out a string, character by character. Words sharing a prefix ("car", "card", "care") share the exact same path down to where they diverge — c, a, r is one shared path all three walk through, only splitting apart at the fourth character. This shared-path structure is the entire mechanism: prefix questions become "walk this many characters down the tree," rather than comparing full strings against each other.

Implementing it: a node is just a dict of children, plus a flag

class TrieNode:
    def __init__(self):
        self.children = {}          # character -> TrieNode
        self.is_end_of_word = False  # True if a real word ends exactly here
 
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_end_of_word = True

Each TrieNode holds a dict mapping "next character" to "the node reached by following it" — this is what lets insert("car") and insert("card") naturally share the same c -> a -> r chain of nodes, only branching where the words actually differ. is_end_of_word matters because a prefix existing in the trie (the path c -> a -> r exists because "card" was inserted) doesn't necessarily mean "car" itself was ever inserted as a real word — that flag is what distinguishes "this is a valid stopping point that's an actual word" from "this is just a node other words pass through."

Searching: walk the path, character by character

def search(self, word):
    node = self.root
    for char in word:
        if char not in node.children:
            return False            # the path doesn't exist at all
        node = node.children[char]
    return node.is_end_of_word        # path exists — but is it a real word, or just a prefix?
 
def starts_with(self, prefix):
    node = self.root
    for char in prefix:
        if char not in node.children:
            return False
        node = node.children[char]
    return True                       # path exists — that's all a prefix check needs

search and starts_with are almost the same walk, differing only in the final check — search requires the ending node to be a real word (is_end_of_word), while starts_with only cares that the path exists at all, since a prefix doesn't need to be a complete word itself. Both run in O(L) time, where L is the length of the word/prefix being checked — genuinely independent of how many words are stored in the trie at all, unlike scanning every stored word to check a prefix.

Why this is a real, non-academic trade-off, not free

Hash set: O(1) exact lookup, but O(n) to find all words with a given prefix
Trie:     O(L) exact lookup (L = word length), O(L + results) to find all words with a prefix

A trie doesn't win at everything — for pure "does this exact string exist" lookups, a hash set is typically simpler and at least as fast. What a trie buys specifically is efficient prefix operations: autocomplete (given "th", suggest "the", "this", "that"), spell-check dictionaries, and IP routing tables (matching the longest prefix of an address) all rely on exactly this "find everything sharing a prefix" capability that a plain hash set structurally cannot provide efficiently.

The concrete signal a trie belongs somewhere

"Autocomplete," "find all words starting with X," "longest common prefix," or "does any word in this dictionary start with this sequence" are the tell — any problem phrased around prefixes specifically, rather than just exact membership. If the actual question is only ever "does this exact string exist," a plain hash set (from the hash-maps lesson) is simpler and does the job without the extra structure a trie requires.