Back to path
IntermediateLexi · Project 5 of 12 ~4.5h· 5 milestones

Autocomplete it with a trie

Continues from the last build: Rung 4 left you with recursive tree walks over sorted titles, exact hash lookups, and range queries, but nothing that can answer a search box typed one letter at a time.

Someone types 'cat' into the search box and pauses, waiting for suggestions before they even finish the word.

Trie data structure designRecursive tree traversalPrefix search algorithmsDepth-first collection orderBig-O reasoning for tree structuresTimed benchmarking with perf_counterMemory footprint reasoningPython dataclasses and type hints
Build this freeBrowse all projectsNo credit card. Already a member?

What you'll build

A Trie class (insert, starts_with) wired into the CLI as a live-suggest REPL, plus a timed benchmark (n, 10n, 100n) showing trie prefix search holding roughly O(k) against the sorted list's growing scan, and a node-count report proving the trie shares memory across common prefixes instead of storing each title in full.

See how we teach, before you sign up

You don't just get code dumped on you. Every starter file and every solution is explained line-by-line, in plain English. Here's one real file from this project:

lexi/trie.pypython
"""Prefix autocomplete built on a trie (rung 5 of Lexi).

Rung 3 gave us a sorted list of titles and bisect() for range queries.
That answers "everything between 'cat' and 'catalog'" but a search box
needs something different: "everything that STARTS WITH 'cat'", fast,
recomputed on every single keystroke as the user types.
"""
from __future__ import annotations
from dataclasses import dataclass, field


@dataclass
class TrieNode:
    """One letter's worth of state. children maps char -> TrieNode."""
    children: dict[str, "TrieNode"] = field(default_factory=dict)
    is_end: bool = False  # without this flag, prefixes leak as if they were real words


class Trie:
    """A branching tree, one node per character position, letters shared."""

    def __init__(self) -> None:
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        """TODO: walk/create a node per character, mark the last node is_end."""
        raise NotImplementedError

    def _find_prefix_node(self, prefix: str) -> TrieNode | None:
        """TODO: walk down from root following prefix; return None if it runs out."""
        raise NotImplementedError

    def starts_with(self, prefix: str, limit: int = 10) -> list[str]:
        """TODO: find the prefix node, then collect completions beneath it."""
        raise NotImplementedError

Reading this file

  • children: dict[str, "TrieNode"] = field(default_factory=dict)Each node maps one character to the next node; no fixed alphabet array, so memory scales with letters actually used.
  • is_end: bool = False # without this flag, prefixes leak as if they were real wordsWithout this flag 'cat' would look like a real title just because 'catalog' passes through its node.
  • def insert(self, word: str) -> None:You will implement this in milestone 1: walk or create one node per character.
  • def starts_with(self, prefix: str, limit: int = 10) -> list[str]:The public API the CLI calls; it composes the prefix walk with a completion collector.

The core structure. Fill in insert and starts_with in the milestones.

That's 1 of 8 explained code blocks in this single project.

The build, milestone by milestone

  1. 1

    Design the node and wire insert

    4 guided steps

    The trie's entire value proposition is that 'cat' and 'catalog' share the same first three nodes. If insert does not reuse existing children, you have just built an expensive list of individual character chains with no sharing at all.

  2. 2

    Walk a prefix and collect completions in the right order

    4 guided steps

    Finding the node is only half the job. A DFS over node.children in dict-insertion order returns completions in whatever order words happened to be inserted, which looks broken to a user expecting something like alphabetical suggestions.

  3. 3

    Wire a live-suggest REPL

    4 guided steps

    This is the moment the trie actually behaves like a search box: type a letter, see suggestions narrow, exactly the interaction a hash index or sorted range scan cannot offer without rebuilding a query every keystroke.

  4. 4

    Benchmark the trie against the sorted-list scan

    4 guided steps

    The whole point of building a new structure is that it is measurably faster for this kind of query. A benchmark on a fixed, small n cannot show that; you need the input to grow to see the trie's near-constant prefix cost pull away from the sorted list's larger scan.

  5. 5

    Analyze memory: node sharing versus raw storage

    4 guided steps

    A trie is not free: every node carries a dict, which costs more per character than a plain Python string. The tradeoff only pays off when titles share enough prefixes for sharing to matter, and reasoning about that (not just assuming tries are always better) is the senior-level takeaway of this rung.

What's inside when you start

3 starter files, ready to clone
5 guided milestones
5 full reference solutions
8 code blocks explained line-by-line
5 "is it working?" checks
4 interview questions it prepares you for

You'll walk away with

trie.py with a working Trie class: insert and starts_with, both correctly handling empty results and case
autocomplete_cli.py, a REPL that suggests live completions as a user types a growing prefix
bench_trie.py, a benchmark printing trie vs sorted-list timings at n = 1,000, 10,000 and 100,000
A short written note (2 to 3 sentences) stating the trie's time complexity for starts_with in terms of prefix length k and result count m, not total titles n

This is portfolio-grade. Build it free.

Sign up to unlock every milestone step-by-step, the code skeletons, full reference solutions, and checkable tasks, with your progress saved as you build.

Start building