Tries

A hash set answers "is carousel in the dictionary" and nothing else. Ask it "which stored words begin with car" and it has no better move than reading all 200,000 entries, because hashing throws away the ordering the question is about. A trie keeps that ordering: a word is a path from the root, one character per step, so every word sharing a prefix shares that part of the path.

The node is a dict and a flag

class TrieNode:
    def __init__(self):
        self.children = {}     # character -> TrieNode
        self.is_end = False    # a word finishes here
        self.top = []          # top-k cache, filled by insert_ranked below

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_end = True

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

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

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

Two fields do the work (top waits for the cache below), and the flag is the one people drop. Without it search("car") returns True for a trie that holds only cartel, because the path exists even though no word ends there. The whole difference between search and starts_with is that one line.

A trie holding car, cart, card and care, with the end-of-word flag marked on four nodes100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

O(length), never O(number of words)

Insert and search touch one node per character: O(L) for a word of length L, with no term for N, the number of words stored. A trie holding 10 words and a trie holding 10 million answer search("card") in the same four steps.

Say the comparison honestly, because the sloppy version invites a correction. A hash set lookup is also O(L) — hashing a string reads every one of its characters. A trie does not beat a hash set at exact lookup and usually loses, because a dict probe is roughly one main memory reference at 100 ns while a four-character walk is four dependent pointer chases at 100 ns each. The trie wins on the questions a hash set cannot answer at all: does anything stored start with this prefix, what are those words, and does anything match this pattern.

What the space costs

Take car, cart, card, care. As four separate strings that is 3 + 4 + 4 + 4 = 15 characters. The trie stores c-a-r once and hangs three leaves off it: 6 nodes under the root. Shared prefixes are paid for once.

The saving is real; the node is not free. With no shared prefixes at all a trie over N words of average length L holds N × L nodes, and a node in Python is an object plus an instance dict plus a children dict — tracemalloc measures the class above at 235 bytes per node built over /usr/share/dict/words, so call it 250. For a 200,000-word English dictionary averaging 8 characters, the raw text is 200,000 × 8 = 1.6 MB. Assume shared prefixes collapse those 1.6 million characters to roughly 500,000 nodes — measured, that dictionary runs 0.35 nodes per character — and at ~250 bytes each that is 125 MB to hold 1.6 MB of text, a 75× multiplier. If you never ask a prefix question you have paid it for nothing, which is the honest answer to "why not always use a trie".

When that bill matters, fix the representation first: __slots__, or a fixed array of children instead of a dict, pulls those 250 bytes back toward 100 without changing the algorithm. Past that, collapse every chain of single-child nodes into one edge holding the whole substring — a radix tree. That is the answer to "how would you shrink this", not the first thing to write.

Autocomplete, and the query that is not O(prefix)

The naive autocomplete is: walk to the prefix node, then depth-first search everything under it and collect words with is_end set. The walk is O(len(prefix)) and the collection is O(size of that subtree) — and for the prefix a that subtree is a large slice of the dictionary.

Put numbers on it. The walk for an 8-character prefix is 8 × 100 ns = 800 ns, under a microsecond. Collecting 20,000 words under a costs roughly 20,000 × 100 ns = 2 ms, about 2,500× more, and it is the half that grows with the dictionary. The structure is fast; the traversal is not.

The fix is to precompute the answer at every node, which is what the third field on TrieNode is for. When you insert a word with a rank — search frequency, say — push it into the top list of each node along its path:

def insert_ranked(self, word, rank, k=5):
    node = self.root
    for ch in word:
        node = node.children.setdefault(ch, TrieNode())
        node.top.append((rank, word))
        node.top.sort(reverse=True)
        del node.top[k:]
    node.is_end = True

A query is now the walk plus a list read: O(len(prefix)), with no subtree scan at all. The bill is one k-element list per node — 500,000 nodes × 5 entries × 4-byte ids = 10 MB on top of the 125 MB, and that figure assumes an array of integer ids, not the (rank, word) tuples the snippet stores for readability. Cheap either way for turning 2 ms into 800 ns. Writes get slower instead: each insert touches L nodes and appends to and re-sorts a k-element list at each — O(k log k) per node, not the O(k) the shape suggests, though bisect.insort into the already-sorted list buys that back. And the cache is stale after a delete, so a deletable dictionary either rebuilds the affected paths or accepts that the cached list is a candidate set to be filtered at read time.

Precompute on write, read a cached answer: this is the waste in the brute force named and removed — the subtree scan repeats work that does not change between queries.

Wildcard search branches at the dot

def search_pattern(self, pattern):
    def walk(node, i):
        if i == len(pattern):
            return node.is_end
        ch = pattern[i]
        if ch == '.':
            return any(walk(c, i + 1) for c in node.children.values())
        nxt = node.children.get(ch)
        return nxt is not None and walk(nxt, i + 1)
    return walk(self.root, 0)

A literal character narrows to one child; a dot fans out to every child that exists. The alphabet-size bound — 26³ = 17,576 paths for three dots — is loose by orders of magnitude, because only branches that exist get walked. The real ceiling is the number of trie nodes at depth ≤ len(pattern): on a 793,000-node trie of English words, walking ... exhaustively reaches 6,982 nodes, not 17,576. The expensive shape is a leading dot: .at starts at the root, where all 26 letters exist, so it does 26 subwalks with nothing to prune them.

This is the shape a trie is for: many stored words, one query. The mirror question — one pattern against one long text — is answered by KMP and the failure function, where building a trie over the text would cost more than the search it saves.

In an interview

The interviewer is testing whether you can say what a trie buys over a hash set, in one sentence, without hand-waving. Say: "Lookup is O(L) for both. The trie is for prefix and pattern queries, and it costs roughly 75× the raw text in memory." That single trade is most of the grade.

Then reach for the second-order point unprompted: the prefix walk is cheap, the subtree collection is not. Most candidates present DFS-from-the-prefix-node as the autocomplete answer and stop. Naming the top-k cache, its 10 MB, and its staleness on delete is the difference between knowing the data structure and having shipped one.

The mistake that loses points: forgetting is_end and then insisting the code is correct. It passes every test where the query word is a leaf and fails the moment a stored word is a proper prefix of another — exactly the car and cart case, which the interviewer will supply.

Check yourself

A trie holds 1 million words. Someone claims lookup is now slower than it was at 1,000 words. Are they right?

No. Both walk one node per character of the query, so the cost is O(L) and independent of N. What does grow is memory and the size of a prefix subtree — so autocomplete for a short prefix gets slower, and exact lookup does not.

You need prefix search over 200,000 words in 8 MB of memory. What do you build?

Not a plain trie — 500,000 nodes at ~250 bytes is about 125 MB. Sort the words and binary search the prefix range instead, but store them as one concatenated blob plus a 200,000-entry array of 4-byte offsets: 1.6 MB + 0.8 MB = 2.4 MB. A Python list of the same 200,000 strings measures 11.4 MB and busts the budget on its own — the str objects, not the characters, are the cost. Each probe is a string comparison, so finding the first match is O(L log n), not O(log n), and the matches are contiguous. A radix tree is the middle option if you must have the trie shape.

c.r returns in under a microsecond and .......... — ten dots — in 20 µs, so wildcard search looks cheap even at full width. Where does that break?

Both stop at the first match, because any() short-circuits: on a 793,000-node trie built from /usr/share/dict/words the ten-dot pattern touched 123 nodes. Ask it to enumerate every match and the same pattern walks 596,180 of those 793,000 nodes and takes 58 ms — 3,000× the existence query. The bound was never 26 per dot compounded; it is the number of trie nodes at depth ≤ len(pattern), capped by the trie itself, and an all-dots pattern as long as a long word reaches most of it. Bound the number of dots, or index words by length and by their fixed characters first.