Tries and Prefix Trees

A hash set answers "is this exact string present?" in $O(1)$ average time, but it has no useful answer for "is there any string starting with AAP?" — it would have to check every stored string individually, $O(n)$ in the count of strings. A trie (from retrieval, pronounced "try") is built specifically to make prefix questions fast: it stores strings as paths through a tree, one character per edge, so all strings sharing a prefix literally share the same path through the tree.

The idea: one path per prefix, shared automatically

Each node in a trie represents a prefix, not a whole string. The root is the empty prefix. Following an edge labeled A from the root reaches the node for prefix "A"; from there, an edge labeled A reaches the node for "AA", and so on. A node is flagged as marking the end of a stored word — some prefixes are also complete words, some are only prefixes of longer ones.

Because every string with a shared prefix reuses the same nodes for that prefix, checking "does any stored string start with X" costs exactly $O(|X|)$ — the length of the prefix — no matter how many strings are stored in the trie. That's the entire value proposition: prefix queries decouple from the size of the dataset.

Worked example: inserting ["CAT", "CAR", "CARD", "DOG"]

Building the trie one word at a time:

• CAT: root → C → A → T (mark T as end-of-word).
• CAR: root → C (exists) → A (exists) → R (new branch off the shared CA prefix, mark end-of-word).
• CARD: root → C → A → R (all exist, shared with CAR) → D (new, mark end-of-word).
• DOG: root → D (new branch straight off the root) → O → G (mark end-of-word).

The path C → A is walked once but shared by three words (CAT, CAR, CARD) — that shared structure is exactly why a query like "any word starting with CA?" costs 2 character-steps regardless of whether 3 or 3 million words share that prefix.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

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

    def insert(self, word):                # O(len(word))
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True

    def starts_with(self, prefix):          # O(len(prefix))
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True

Where it shows up

Interviewers ask for "implement Trie," "word search II" (finding multiple dictionary words in a grid), and autocomplete-style problems where a trie is the intended structure rather than a hash set. In quant systems, tries show up in ticker/symbol autocomplete for a trading UI, in matching instrument identifiers by prefix (exchange codes, ISIN stems), and more generally anywhere a system needs fast "does anything match this prefix" lookups over a large, static-ish vocabulary — a role a plain hash-based set cannot fill efficiently.