Exercises — Trie (prefix tree) — insert, search, startsWith, applications (autocomplete, spell check)

Walk every distinct path and count each circle once:

• root — 1
• c, a, r — 3 (the shared spine of car, card, care)
• d (child of r, ending card) — 1
• e (child of r, ending care) — 1
• d, o, g (the dog branch) — 3

Total $=1+3+1+1+3=9$ nodes. WHY the sharing matters: car, card, care cost only 3 spine nodes plus 2 branch tips, not $3+4+4=11$ separate letters. That collapse is the trie's benefit.

A word finishes at the last-letter node of each inserted word: car (the r), card (the d), care (the e), dog (the g). That is $4$ — exactly one per inserted word, always. The amber dots in the figure mark them.

Walk the letters: root $\to$ c (exists) $\to$ a (exists) $\to$ r (exists) $\to$ e (exists). We consumed all 4 characters with no broken step, landing on the e node. Now the deciding check: is e.isEnd True? Yes — care was inserted, so e is amber. Return $\mathbf{True}$.

search("ca"): root $\to$ c $\to$ a. Path exists, so we reach the a node. Final question: is a.isEnd True? No — we never inserted the word ca; a is just a passing point. Return $\mathbf{False}$. startsWith("ca"): same walk to a, but this operation ignores isEnd entirely and asks only "did the road survive?" The road survived, so return $\mathbf{True}$. The single-line difference (return node.isEnd vs return True) is the whole distinction.

Walk cart on the reference trie: c (exists) $\to$ a (exists) $\to$ r (exists) $\to$ then need child t of r. The r node currently has children d and e but no t. So create exactly 1 new node, the t under r, and set t.isEnd = True. Only $1$ new node — because car is a shared prefix already paved. The new node count equals the number of new characters, which is $L$ minus the length of the longest already-existing prefix ($4-3=1$).

No shared prefixes means no path is ever reused — each word gets its own private chain of $L$ nodes. So excluding the root: $\mathbf{N}\cdot \mathbf{L}$ nodes. Including the root: $\mathbf{N}\cdot \mathbf{L}+1$. This is the trie's worst case for space: nothing is shared, so it degenerates into $N$ separate strands hanging off one root — no better than storing the strings separately, plus the overhead of node objects.

Each word is a prefix of the next, so they walk the same single chain and only ever add one node at the tip:

• a: create node a (mark end). Nodes: root, a $\to 2$.
• ab: a exists, add b. $\to 3$.
• abc: add c. $\to 4$.
• abcd: add d. $\to 5$.

Final count including root $=5$. Notice all four of a, b, c, d are amber (isEnd) — four words, four flags, one chain. This is the best case for sharing: nested prefixes.

isEnd nodes: a, b, c, d — that is $4$. Leaves (nodes with no children): only d at the very tip — that is $1$. Mismatch: 4 words but 1 leaf, because every word except the longest ends at an internal node. This is the crispest proof of why "leaf = word" fails and isEnd is mandatory.

search visits exactly one node per query character — at most $L$ steps — and each step is a single child lookup that does not care how many words are stored. So the time is $\mathbf{O}(\mathbf{L})$, independent of $N$: a million stored words don't slow one lookup. A Binary Search Tree of strings does $O(\log N)$ node comparisons, but each comparison compares strings character by character, costing up to $O(L)$. Total $O(L\log N)$. For large $N$ the trie's $O(L)$ wins because it never re-pays the $\log N$ factor. (A Hash Table also gives $O(L)$ membership but, as the parent stressed, cannot answer prefix queries at all.)

Walk the prefix car: root $\to$ c $\to$ a $\to$ r. We stand on the r node. Now DFS the subtree, emitting a word whenever isEnd is True. Path accumulated so far is car.

• r.isEnd is True $\Rightarrow$ emit car.
• Explore children of r alphabetically: d before e.
  • Enter d: d.isEnd True $\Rightarrow$ emit card. d has no children.
  • Enter e: e.isEnd True $\Rightarrow$ emit care. e has no children.

Result: $[\text{car},\text{card},\text{care}]$. Note dog never appears — the DFS started inside the relevant subtree, so it physically cannot reach unrelated branches. That pruning is why autocomplete is fast.

Idea: walk to the prefix node (like startsWith); if the walk breaks, return 0. Otherwise DFS the subtree and count every isEnd.

def countWordsWithPrefix(self, prefix):
    node = self.root
    for c in prefix:
        if c not in node.children:
            return 0            # road broke ⇒ zero words
        node = node.children[c]
    count = 0
    def dfs(n):
        nonlocal count
        if n.isEnd:
            count += 1
        for child in n.children.values():
            dfs(child)
    dfs(node)
    return count

For "ca": walk to the a node. DFS its subtree hits isEnd at r (car), d (card), e (care) = $3$ words. Evaluating countWordsWithPrefix("ca") = 3. (Production tip: store a running prefixCount integer in each node during insert to make this $O(L)$ instead of $O(\text{subtree size})$.)

search("cet"): root $\to$ c (exists) $\to$ need child e of c. The c node's only child is a. Path breaks at character 2 $\Rightarrow$ return $\mathbf{False}$. So cet is flagged as misspelled. Suggestion via Edit Distance $\le 1$: allow one substitution/insertion/deletion while walking. Substituting the e for an a matches the existing a edge and continues c$\to$a$\to$t reaching cat (isEnd True) with exactly 1 edit. So the suggestion is cat. The trie prunes the search: the moment a partial path exceeds the budget, its whole subtree is skipped — you never explore dog-like unrelated branches.

Trie before: root$\to$c$\to$a$\to$r(isEnd, word car)$\to$d(isEnd, word card). Delete card: unset d.isEnd. Now d is a leaf with no isEnd and belongs to no word $\Rightarrow$ remove node d. Walk back up: r still has isEnd = True (it's the word car) $\Rightarrow$ stop, keep r, a, c, root. Only 1 node removed. Delete car (from the original two-word trie): unset r.isEnd. But r still has child d (for card) $\Rightarrow$ r is not prunable; keep it. Nothing is physically removed — you only cleared a flag. Rule: on delete, always just unset isEnd; prune a node only if it has no children and is not another word's end, walking upward until that condition fails.

(a) search(""): the loop over characters runs zero times, so node stays the root. Return root.isEnd. This is True only if the empty string was inserted, otherwise False. Answer: $\text{root.isEnd}$. (b) startsWith(""): zero-iteration loop leaves node at root; return True. Every trie "starts with" the empty prefix, always True. (c) insert(""): zero-iteration loop, then root.isEnd = True. It legitimately marks the empty string as a stored word — no new nodes created. This is exactly why the empty-string case is unambiguous and why search("") depends on whether this was done.

(a) Hash Table — $O(L)$ membership, no tree overhead; but it cannot do prefixes, which is fine here. (b) plain Trie — $O(L)$ lookups independent of $N$, and prefix queries are its native strength. (c) Radix Tree (Compressed Trie) — merges long single-child chains into one edge, killing the per-character node overhead a plain trie suffers on words like internationalization. (d) Suffix Tree — built over all suffixes of $T$, it answers "is $P$ a substring?" in $O(L)$; a prefix trie of words cannot, since substrings aren't prefixes. (Related: Longest Prefix Match is the routing cousin of these prefix walks.)