Lesson 26 · Trees & graphs

Tries — prefix queries in O(L)

📖 Walk me through it — plain English

A trie (rhymes with "try," also called a prefix tree) is a tree where each step down the tree adds one character. To store the word "cat," you make a chain of nodes: root → c → a → t. Words that share a beginning share the same nodes near the top — "cat" and "car" both walk through the same c and a nodes, then split. This is exactly why a trie is fast for any question about prefixes (the first few letters of a word): the shared prefix is stored once.

In this lesson the trie is built from plain nested dictionaries (hash maps). Each node is a dictionary whose keys are the next possible characters and whose values are the child nodes. One special key, '$', is parked in a node to mean "a complete word ends right here." Without that marker we couldn't tell a full word from a mere prefix — both "car" and "cards" pass through the r node, so the r node needs '$' to say "car is a real word," and the path keeps going to store "cards."

Analogy: think of a filing cabinet of street signs. The top drawer splits by first letter, the next drawer by second letter, and so on. To check if a street exists you just follow the labeled drawers one letter at a time. Streets that start the same way share the same opening drawers — you never re-file the common part.

The three operations all reuse one helper, _walk, which simply follows the characters one at a time. If a character is missing it returns nothing. insert walks and creates missing children with setdefault (give me this key, or make an empty dict if absent), then drops the '$' marker. search(w) walks and checks '$' is present (full word). starts_with(p) walks and just checks we landed somewhere (prefix exists). Let's trace inserting "cat" then "car," and answering three queries.

Step 1 · insert("cat"). Start at the root (empty dict, shown as ·). Read 'c'; it is not a key yet, so setdefault creates an empty child dict and we move into it. The 'c' node is now active.

Step 2 · still inserting "cat". Read 'a' (create child, move in), then 't' (create child, move in). We have walked the whole word, building the chain root → c → a → t.

Step 3 · finish "cat". At the 't' node, set the key '$' = True to mark that a complete word ends here. Green means "this node carries the '$' word-end marker."

Step 4 · insert("car"). 'c' and 'a' already exist, so we reuse them (the shared prefix, top row). At 'a' we look for 'r' — it is new, so the 'a' node now branches into two children: the old 't' (from "cat") and the new 'r'. Mark '$' at 'r'. The bottom row shows those two siblings; both are word-ends ("cat" and "car"), and the 'c'/'a' prefix above is stored only once.

Step 5 · search("car"). Walk c → a → r, every character found. We landed on the 'r' node and it has the '$' marker, so "car" is a stored word. Answer: True.

Step 6 · search("ca"). Walk c → a — both characters found, so we land on the 'a' node (active below). But the 'a' node has no '$' marker, so "ca" is only a prefix, not a stored word: search returns False. Note starts_with("ca") would return True, since we did land somewhere.

Step 7 · search("cab"). Walk c → a, then look for 'b' as a key of the 'a' node — it is not there (struck out). _walk returns None immediately, so the answer is False without scanning any further.

Why it is fast: every operation does one dictionary lookup per character and nothing else. For a word of length L that is L steps, so the cost is O(L) — it does not depend on how many words are stored. Whether the dictionary holds 10 words or 10 million, searching "car" still takes 3 hops. The number of words only affects memory (how many nodes exist), not the time to look one up.

Why the '$' marker matters: it is the single line that separates "this is a real word" from "this is just the start of longer words." That one idea is what powers autocomplete (walk to the prefix node, then explore everything below it), word-existence checks, and "longest matching prefix in a dictionary" — all in O(L).

A trie is just a tree where edges are characters. Autocomplete, word search, "longest prefix in a dictionary" all collapse to a 20-line trie.

Visual — trie of {"cat", "car", "cards"}

Green = isEnd. Walk down to query; insert by extending.

Template — Trie

class Trie:
    def __init__(self):
        self.root = {}                  # nested dicts; '$' marks word-end

    def insert(self, w):
        node = self.root
        for ch in w:
            node = node.setdefault(ch, {})
        node['$'] = True

    def search(self, w):
        node = self._walk(w)
        return node is not None and '$' in node

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

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

class Trie {
  root: any = {};
  insert(w: string) {
    let n = this.root;
    for (const ch of w) n = (n[ch] ??= {});
    n.$ = true;
  }
  search(w: string) { const n = this._walk(w); return !!n && n.$ === true; }
  startsWith(p: string) { return this._walk(p) !== null; }
  _walk(s: string) {
    let n = this.root;
    for (const ch of s) { if (!(ch in n)) return null; n = n[ch]; }
    return n;
  }
}

Where it wins: autocomplete (walk to prefix node, DFS to collect words). Word Search II: trie of words + DFS on grid simultaneously. Replace words: walk each word against the dictionary trie, stop at first word-end.

Count dictionary words with a given prefix — build a trie and walk it:

→ Going deeper: Tries specialize the string algorithms. See String matching (KMP, hashing).