Tries

When to reach for it

• Autocomplete and typeahead: the words or queries that start with what the user typed.
• Many lookups against a fixed dictionary, especially by prefix.
• Longest-prefix matching: routing tables, address blocks, URL rules.
• Searching a grid of letters for many words at once, stopping as soon as no word has the current prefix.

The core idea

Each node maps a character to a child node and carries a flag that marks the end of a word. Inserting walks down from the root, creating nodes as needed. Looking up walks down and fails as soon as a character is missing. Two words that share a prefix share those nodes, so the structure answers prefix questions that a hash set cannot.

The power is in what you keep on the nodes. Keep a count to answer "how many words have this prefix" instantly. Keep the few best completions at each node to answer autocomplete without walking a large subtree, and pay for it by updating those lists on insert. Say that trade-off out loud; it is usually the follow-up question.

A Python template

class TrieNode:
    __slots__ = ("children", "is_word", "count")
    def __init__(self):
        self.children = {}       # char -> TrieNode
        self.is_word = False     # a word ends exactly here
        self.count = 0           # words that pass through here

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
            node.count += 1
        node.is_word = True

    def _walk(self, prefix):
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def contains(self, word):
        node = self._walk(word)
        return bool(node and node.is_word)

    def count_prefix(self, prefix):
        node = self._walk(prefix)
        return node.count if node else 0

Time and space

Insert and lookup cost O(m) for a word of length m, whatever the number of words stored. Space is O(total characters) in the worst case, the price of that speed. Listing every completion of a prefix costs O(m plus the size of the subtree), which is why real autocomplete caches the top completions per node.

Common mistakes

• Treating "the prefix exists" as "the word exists"; the end-of-word flag is what tells them apart.
• Walking the whole subtree on every keystroke when the subtree is large.
• Inserting text without normalizing case and spacing, so one query lands on two paths.
• Using a fixed 26-slot array when the input can contain other characters.
• Not comparing the memory cost with a sorted list and binary search, which also answers prefix ranges.

How to explain it out loud

Explain why a trie beats a set here: "A set tells me whether a whole word exists, but not which words start with ca. A trie answers that by walking at most the length of the prefix." The comparison shows you chose the structure for a reason, which is the heart of approach planning.

Then say what each node stores and why, especially anything cached for speed, and what it costs on insert. Trace inserting two words that share a prefix and looking up a third. Raising normalization and memory before you are asked is the edge-case thinking Devana's rubric rewards.