Tries (Prefix Trees)

A trie — said “try”, from retrieval — is a tree where the path from the root spells out a string.

To store "cat", you walk down from the root along c, then a, then t, and mark that last spot as the end of a word. To store "car", you walk c, a, then r. Notice what just happened: the c → a part of the path was already there from "cat", so the two words share it. That shared-prefix sharing is the entire idea of a trie, and everything good about it follows from there.

One picture

Here is the trie after inserting cat, car, card, do, and dog. Green nodes mark where a complete word ends:

A node can be both an end-of-word and keep going: do ends at the o, yet dog continues through that same o. The root stands for the empty prefix; each step down adds one character.

Why the cost ignores the dictionary

Let L be the length of a word. Then insert is O(L), exact lookup is O(L), and prefix search is O(L) to reach the prefix plus O(k) to gather its k completions.

The striking thing is what is missing from those costs: the number of words in the trie. A lookup never compares your query against other words — it just follows one edge per character, steered entirely by the query itself. Whether the trie holds ten words or ten million, looking up an 8-letter word walks exactly 8 edges. A hash set also gives O(1) lookup, but it has no structure to exploit for “every word starting with ca” — it would have to scan every key. A trie answers that with a single subtree walk. The trade is memory: a trie spends nodes to buy cheap prefix queries.

Building one in Python

The cleanest version is a dictionary of dictionaries — each node maps a character to its child node, and a sentinel key marks the end of a word:

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})   # walk, creating nodes as needed
        node["$"] = True                     # mark end-of-word

    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node:
                return False
            node = node[ch]
        return "$" in node                   # reached the end — but is it a word?

    def startswith(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node:
                return False
            node = node[ch]
        return True                          # reached the prefix — a subtree exists

t = Trie()
for w in ["cat", "car", "card", "do", "dog"]:
    t.insert(w)

print(t.search("car"))       # a stored word
print(t.search("ca"))        # only a prefix, not a word
print(t.startswith("ca"))    # but words do start with it
print(t.startswith("dx"))    # nothing starts with "dx"

True
False
True
False

The "$" sentinel works because it can never be a real character edge, so it cleanly distinguishes “a word ends here” from “the path merely continues.” (A dedicated is_end flag on a node class does the same job, a touch more tidily.)

When a trie beats a hash map

Reach for a trie when prefix queries matter — autocomplete, type-ahead, URL routing — or when a shared prefix is worth compressing (50,000 words starting with un store that prefix once, not 50,000 times), or when you want alphabetical order for free (a depth-first walk of a trie visits words sorted). Reach for a plain hash set when you only ever need exact-match lookup and memory is tight.

Practice