Basic Trie Questions

1. Count how many stored words have a given prefix

Add a count to each node: increment it for every node you pass through during insert. Then “how many words start with pre?” is just “walk to the pre node and read its count” — O(L).

class Node:
    def __init__(self):
        self.children = {}
        self.count = 0          # words passing through this node
 
class PrefixCounter:
    def __init__(self): self.root = Node()
    def insert(self, word):
        cur = self.root
        for c in word:
            cur = cur.children.setdefault(c, Node())
            cur.count += 1       # every node on the path counts this word
    def count_prefix(self, prefix):
        cur = self.root
        for c in prefix:
            if c not in cur.children: return 0
            cur = cur.children[c]
        return cur.count

The trick — maintain the aggregate on the way down — generalizes: store sums (Map Sum Pairs), maxima, or any associative quantity at each node.

2. Autocomplete — first k words for a prefix

Walk to the prefix node, then DFS the subtree in sorted order, stopping after k words. Covered in full on the operations page — the engine behind Search Suggestions System.

3. Longest common prefix of a set of words

Insert all words; then walk down from the root as long as there’s exactly one child and the node isn’t end-of-word. The path you walk is the LCP.

def longest_common_prefix(words):
    if not words: return ""
    root = {}
    for w in words:                       # build a minimal trie
        node = root
        for c in w: node = node.setdefault(c, {})
        node["$"] = True                  # end marker
    lcp, node = [], root
    while len(node) == 1 and "$" not in node:
        c = next(iter(node))
        lcp.append(c); node = node[c]
    return "".join(lcp)

The LCP ends the moment the path branches (more than one child) or a word ends (the shortest word is itself the limit). This is the trie lens on Day 2’s Longest Common Prefix.

4. Does the trie contain any word at all?

Trivial but instructive: a trie is non-empty iff the root has children. More useful: “is this node a leaf?” (no children) tells you a word ends here with nothing after it — handy in deletion and word-break problems.

5. Count distinct substrings of a string (preview)

Insert all suffixes of a string into a trie. The number of nodes (excluding the root) equals the number of distinct substrings — because every distinct substring is a unique root-to-some-node path. O(n²) nodes naively; the optimal version uses a suffix automaton/tree, but the trie framing is the intuition.