Project: Building Autocomplete with a Trie

Build the mental model

A Trie stores a set of words by sharing common prefixes as a path from the root: each node represents one character, and any word inserted corresponds to a path from root to a node marked 'end of word.' The naive alternative for autocomplete is scanning a flat list of all tutorial titles and checking `.startswith(prefix)` on each one — correct but O(n) in the number of stored words every single keystroke, which gets slow as the catalog grows and wastefully re-examines words that share nothing with the typed prefix. A Trie instead walks exactly `len(prefix)` nodes to reach the subtree containing every matching word, then collects results only from that subtree — cost proportional to the prefix length plus the number of matches, not the total vocabulary size. This is precisely why search-autocomplete systems use Tries (or compressed variants like radix trees) rather than filtering full lists: the shared-prefix structure means work is never repeated across words that branch off the same stem, and lookups stay fast as the word set scales into the thousands.

Connect it to a real scenario

This project is not an analogy — it directly models the Tutorial Platform's real `/api/search-suggest` endpoint. That endpoint answers exactly this question: given what a user has typed so far ('post', 'prompt'), which tutorial slugs and titles from `search-index.json` start with that prefix? A Trie built once from every entry in `search-index.json` (each lesson/tutorial title inserted as a word) turns each keystroke's suggestion lookup into an O(prefix length) walk instead of re-scanning the whole index file on every request. Since `search-index.json` must already be rebuilt with `pnpm build-search-index` before deploy, the natural place to build this Trie is at server startup or at build time, caching it in memory for the life of the process.

A Trie shares path prefixes across words, so lookup costs O(prefix length + number of matches)
A flat-list `.startswith` scan costs O(n) per keystroke and slows down as the tutorial catalog grows
This Trie directly models the site's real `/api/search-suggest` endpoint and `search-index.json`

Try the working example

python

class TrieNode:
    def __init__(self):
        self.children = {}   # char -> TrieNode
        self.is_end = False

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

    def insert(self, word: str):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True

    def _collect(self, node, prefix, results):
        if node.is_end:
            results.append(prefix)
        for ch, child in node.children.items():
            self._collect(child, prefix + ch, results)

    def autocomplete(self, prefix: str):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return []  # no word in the index starts with this prefix
            node = node.children[ch]
        results = []
        self._collect(node, prefix, results)
        return sorted(results)

# Simulates entries loaded from search-index.json
tutorial_slugs = ["python", "postgresql", "prompt-engineering", "playwright", "rust"]

trie = Trie()
for slug in tutorial_slugs:
    trie.insert(slug)

print(trie.autocomplete("p"))
print(trie.autocomplete("post"))

You should see

Prints `['playwright', 'postgresql', 'prompt-engineering', 'python']`, then prints `['postgresql']`.

5-minute try-it

Store a popularity/search-count on each end-of-word node and modify `autocomplete()` to rank results by popularity instead of alphabetical order.

One important caution

Forgetting to check `is_end` when collecting results means a prefix that is itself an inserted word (e.g. 'post' inserted alongside 'postgresql') can be silently dropped from the output

Using 'does this node have children' instead of an explicit `is_end` boolean to detect word endings breaks as soon as one inserted word is a prefix of another — 'post' would never register as a complete word since its node still has children from 'postgresql'

Wikipedia — Trie — Data Structures & Algorithms