Tries (Prefix Trees)

Insert "cat", "car", and "dog" into a trie:

(root)
 ├─ c ─ a ─ t●
 │        └─ r●
 └─ d ─ o ─ g●

"cat" and "car" share the path c → a and split only at the last letter; ● marks "a word ends here." Two consequences fall out of the picture:

• Shared prefixes are stored once. A million words starting with "un" store that "un" exactly one time.
• Every node is a prefix. Walking k characters lands you at the node representing that k-character prefix — and the subtree below it contains exactly the words that start with it.

The end-of-word marker is not optional decoration: without it, inserting "cattle" would make "cat" look like a word (or not — you couldn't tell). Node existence means prefix; the flag means word.

Skip the TrieNode class ceremony — in Python, a node is just a dict mapping character → child node, with a sentinel key marking word ends:

END = "$"          # sentinel — can't collide with a real character

def insert(root, word):
    node = root
    for ch in word:
        node = node.setdefault(ch, {})   # walk, creating as needed
    node[END] = True

def search(root, word):                  # exact word?
    node = root
    for ch in word:
        if ch not in node:
            return False
        node = node[ch]
    return END in node

def starts_with(root, prefix):           # any word with this prefix?
    node = root
    for ch in prefix:
        if ch not in node:
            return False
        node = node[ch]
    return True

search and starts_with are the same walk with different finishes — one checks the flag, the other only needs to arrive. Every operation is O(L) in the length of the string, independent of how many words the trie holds. setdefault does insert's create-or-descend in one call; it's the trie author's best friend.

A hash set already gives O(L) exact lookup — hashing must read all L characters anyway. So when does a trie earn its keep?

The structural reason: a hash function scatters "car" and "cat" to unrelated buckets — by design, since uniform scattering is what makes hashing fast. The trie does the opposite: it clusters strings by shared prefix, so one short walk reaches the entire family. Neither wins everywhere; the trie wins exactly when the question is about prefixes, not whole strings.

It also unlocks moves hashing can't express: walk a trie while DFS-ing a letter grid and you prune entire search branches the moment a path stops being a prefix of any word — the trick behind multi-word boggle/word-search problems.

Frame the search-box feature as operations you now own:

1. Walk the prefix — O(len(prefix)) to reach the node for what the user typed. Dead end ⇒ zero suggestions, instantly.
2. Enumerate the subtree — DFS below that node yields every completion. Unbounded, so…
3. Rank and cut — keep popularity counts and return the top k. Either heap-select over the subtree, or precompute "top k per node" at insert time to make reads O(len(prefix) + k).

That third step is a real engineering trade-off — precompute at write time vs compute at read time — and it's exactly the conversation a "design typeahead / search suggestions" system-design interview (week 6) wants. There, the trie gets sharded across machines by prefix, hot prefixes get cached, and rankings refresh offline — but the data structure at the core is the one you just built from dicts.

When to reach for a trie in a coding round: many strings + repeated prefix-shaped questions (autocomplete, longest shared prefix, shortest root, wildcards). One-shot exact membership? Stay with the hash set — simpler and cache-friendlier.