Autocomplete Like a Jedi: Building a Trie from Scratch

The Quest Begins (The "Why")

I still remember the first time I was asked in an interview to “return all words that start with a given prefix.” My brain went straight to the obvious solution: loop through the whole dictionary, check each word with startsWith, and collect the matches. It worked… until the interviewer smiled and said, “What if we have a million words?” Suddenly my O(N × L) loop felt like trying to defeat a dragon with a toothpick.

That moment sparked a quest. I needed a data structure that could answer prefix queries in time proportional to the length of the prefix, not the size of the dictionary. Enter the Trie—sometimes called a prefix tree. It’s the kind of tool that feels like finding a lightsaber in a junkyard: simple, elegant, and ridiculously powerful once you know how to wield it.

The Revelation (The Insight)

So why does a Trie make autocomplete fast?

Think of every word as a path from the root of a tree, where each edge is a character. The root represents the empty prefix. As you walk down the tree, the letters you’ve traversed spell out the prefix you’ve seen so far. Every node therefore embodies a unique prefix, and all words that share that prefix live in the subtree beneath it.

If you want to know all completions for “cat”, you just:

1. Walk from the root following c → a → t.
2. If you can’t follow the path, there are no words with that prefix.
3. If you can land on the node for “cat”, every word in its subtree is a valid answer.

Now the work is only:

• O(P) to walk the prefix (P = prefix length).
• O(K) to gather the K results by a depth‑first search of that subtree.

No scanning of unrelated words, no wasted comparisons. The Trie stores each character exactly once, so building it costs O(total characters) across all words—linear in the input size.

That’s the magic: the structure itself encodes the prefix relationship, turning a costly filter into a simple walk‑and‑collect.

Wielding the Power (Code & Examples)

Let’s build a minimal Trie that supports insertion and autocompletion. I’ll use Python because it’s readable, but the same ideas translate to any language.

class TrieNode:
    __slots__ = ("children", "is_word")   # saves a bit of memory
    def __init__(self):
        self.children = {}                # char -> TrieNode
        self.is_word = False              # marks end of a inserted word

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

    def insert(self, word: str) -> None:
        """Add a word to the Trie."""
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_word = True               # flag the terminal node

    def _find_node(self, prefix: str) -> TrieNode | None:
        """Return the node representing the prefix, or None if missing."""
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

    def _dfs_collect(self, node: TrieNode, prefix: str, results: list) -> None:
        """Depth‑first walk adding every word found under `node`."""
        if node.is_word:
            results.append(prefix)
        for ch, child in node.children.items():
            self._dfs_collect(child, prefix + ch, results)

    def autocomplete(self, prefix: str) -> list:
        """Return all words in the Trie that start with `prefix`."""
        node = self._find_node(prefix)
        if node is None:
            return []                     # no matches
        results = []
        self._dfs_collect(node, prefix, results)
        return results

Why This Works (Again, with Feeling)

Insertion walks each character once—O(L) per word, where L is the word length. Over n words the total is O(Σ Lᵢ), i.e., linear in the total number of characters.

Autocomplete does two phases:

1. Prefix walk – at most P steps (the length of the query).
2. DFS – visits only nodes that belong to words with that prefix. If there are K matching words and the average extra length beyond the prefix is M, the work is O(K · M), which is essentially the size of the output.

In big‑O terms we can say O(P + output size)—optimal because you must at least look at the prefix and touch each result once.

Common Traps (The “Don’t Step on the Lava” Moments)

Mistake	What Happens	Fix
Using a fixed‑size array for children (e.g., 26 slots) when the input can contain Unicode or digits	Wastes memory or breaks on unexpected chars	Keep a dict (defaultdict or plain {}) – it grows only with needed branches
Forgetting to set is_word = True on the terminal node	Words are inserted but never recognized as complete	Always mark the end after the loop
Modifying the prefix string inside the DFS (e.g., prefix += ch) without backtracking	Results get garbled because the same string object is reused	Pass prefix + ch (creates a new string) or use a list buffer with push/pop
Returning the raw node list instead of the assembled words	Caller gets internal structures, not usable strings	Collect words as shown in _dfs_collect

Real‑World Interview Flavors

1. “Prefix Search” – Given a list of strings, return all that start with a query. This is exactly what autocomplete solves. Interviewers love it because it tests whether you can move from brute force to a Trie.

2. “Longest Word in Dictionary” (LeetCode 720) – Find the longest word that can be built one character at a time by other words in the list. A Trie lets you verify each prefix exists in O(L) time per word, turning an O(N²·L) check into O(N·L).

Both problems illustrate how the same core idea—prefix existence—unlocks multiple challenges.

Why This New Power Matters

Armed with a Trie, you can now:

• Build instantaneous search suggestions for an IDE, a mobile keyboard, or a web search bar.
• Implement routing tables for network prefixes (think IP address lookup).
• Solve a slew of string‑based interview puzzles with confidence, knowing you’ve got a sub‑linear tool in your belt.

The best part? The structure is tiny enough to fit in memory for most realistic dictionaries, yet it scales gracefully. You’ve turned a “search through everything” slog into a targeted trek—just like a Jedi using the Force to sense where the lightsaber lies, instead of swinging blindly.

Your Turn

Grab a list of your favorite movie titles, song names, or even GitHub repo names. Insert them into a Trie and try out different prefixes. Notice how the suggestions appear instantly, no matter how large the list grows.

Challenge: Extend the Trie class to return results sorted by frequency (i.e., keep a count at each node and prioritize higher‑frequency words). Share your solution in the comments—let’s see who can build the most polished autocomplete!

May your prefixes be ever in your favor. 🚀