Building Autocomplete from Scratch: My Journey with the Trie (aka the Jedi Library)

The Quest Begins (The "Why")

I still remember the first time I tried to implement autocomplete for a side‑project. I had a list of 200 k product names, a naive filter that scanned the whole array on every keystroke, and a UI that froze harder than a boss fight in Dark Souls after you forget to upgrade your weapon. Every time the user typed a letter, the browser would chug, the dev tools would scream about long‑running scripts, and I’d stare at the spinner wondering if I’d ever make it past the interview question “Design an autocomplete feature”.

The problem wasn’t that I didn’t know how to filter strings; it was that I was doing O(N × L) work for each query, where N is the number of words and L the average length. For a modest dictionary that’s okay, but for anything that feels like a real product it’s a non‑starter. I needed a data structure that could skip over whole chunks of words that share no prefix with the query—something that let me jump straight to the relevant subtree.

That’s when the Trie popped up on my radar, and honestly, it felt like discovering a hidden shortcut in a Metroidvania map. Suddenly, the impossible became doable.

The Revelation (The Insight)

So why does a Trie work so well for prefix‑based look‑ups? Imagine you have a bunch of words written on index cards and you stack them according to their first letter, then within each stack you further split by the second letter, and so on. You end up with a tree where every node represents a prefix, and every path from the root to a node spells out a word (or a prefix of a word).

The magic is that all words that share a prefix live in the same subtree. If I’m looking for suggestions for “aut”, I don’t need to glance at words that start with “b”, “c”, or “z”. I simply walk down the tree following the letters a → u → t, and from that node I can collect every descendant word. The work I do is proportional to the length of the prefix plus the number of results I actually return—not the size of the whole dictionary.

In algorithm‑speak:

• Insertion of a word of length L: O(L) – we walk/create L nodes.
• Search for a prefix of length P: O(P) – we just follow the path.
• Collecting all completions: O(P + K) where K is the total characters in the output (or O(number of words × average length) if you prefer to count words).

That’s linear in the size of the input we actually care about, not the size of the entire dataset. For an interview, that’s the kind of answer that makes the interviewer lean back and say, “Nice, you actually get it.”

Wielding the Power (Code & Examples)

The Struggle – Naïve Filter

// DON'T DO THIS IN PRODUCTION
function naiveAutocomplete(query, dictionary) {
  return dictionary.filter(word => word.startsWith(query));
}

If dictionary has 200 k entries and the user types “a”, we still scan 200 k strings. On a mobile device that’s a janky UI and a frustrated user.

The Victory – Trie‑Based Autocomplete

Below is a compact, production‑ready Trie implementation in JavaScript (feel free to port to your language of choice). I’ve added comments that call out the “traps” I fell into the first time around.

class TrieNode {
  constructor() {
    // children maps a character to the next TrieNode
    this.children = new Map();
    // marks the end of a word
    this.isWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  // Insert a word – O(L)
  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) {
        node.children.set(ch, new TrieNode());
      }
      node = node.children.get(ch);
    }
    node.isWord = true;
  }

  // Find the node that corresponds to the prefix – O(P)
  _findNode(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children.has(ch)) return null; // prefix not present
      node = node.children.get(ch);
    }
    return node;
  }

  // Return all words that start with prefix – O(P + K)
  autocomplete(prefix) {
    const node = this._findNode(prefix);
    if (!node) return []; // no matches

    const results = [];
    const dfs = (current, path) => {
      if (current.isWord) results.push(path);
      for (const [ch, child] of current.children) {
        dfs(child, path + ch);
      }
    };
    dfs(node, prefix);
    return results;
  }
}

// Usage
const trie = new Trie();
['apple', 'app', 'application', 'apt', 'banana', 'band', 'bandana']
  .forEach(w => trie.insert(w));

console.log(trie.autocomplete('ap')); // ['app', 'apple', 'application']
console.log(trie.autocomplete('ba')); // ['banana', 'band', 'bandana']
console.log(trie.autocomplete('z'));  // [] – quick exit

Traps to Avoid

1. Forgetting to mark isWord – If you don’t set the flag when you finish inserting a word, your DFS will miss exact matches (e.g., searching for “app” would return only longer words).
2. Using a plain object for children and accidentally hitting prototype keys – A Map avoids the __proto__ gotcha that can cause weird bugs when a word contains a character like "__proto__".
3. Recursive DFS on a huge dictionary – In practice you might want an iterative stack or a generator to avoid hitting the call‑stack limit on very long words. For interview purposes, recursion is fine and keeps the code readable.

Real‑World Interview Flavors

• LeetCode 208 – Implement Trie (Prefix Tree) – Classic. You’re asked to build insert, search, and startsWith. The follow‑up often is “return all words with a given prefix”, which is exactly our autocomplete.
• Google Phone Screen – Design a search suggest feature – You discuss trade‑offs (hash‑set vs. Trie vs. ternary search tree). The Trie wins when you need prefix‑based results and you care about memory sharing of common prefixes.

Why This New Power Matters

Armed with a Trie, you can turn a sluggish, O(N × L) filter into a blazing‑fast, O(P + K) suggestion engine. Suddenly:

• Mobile apps stay buttery smooth even with dictionaries of hundreds of thousands of entries.
• Interviewers see you think beyond the obvious solution and appreciate your grasp of algorithmic trade‑offs.
• You get to build cool features—like a search bar that predicts what you’re typing before you finish the word, just like the Jedi sensing disturbances in the Force.

The best part? The structure is tiny. Each node only stores a map of its children and a boolean flag. For English words, the memory overhead is often lower than storing the full list because shared prefixes aren’t duplicated.

Your Turn – The Challenge

Grab a list of your favorite movie titles, video‑game names, or even a CSV of city names. Insert them into a Trie and build an autocomplete box that updates as you type. Try adding a “debounce” layer so you don’t call the autocomplete on every single keystroke, and watch how the Trie keeps the backend work negligible no matter how fast the user types.

When you see those suggestions appear instantly, remember: you’ve just wielded the power of the Jedi Library. May your code be ever efficient and your bugs be few! 🚀

---

Happy coding, and may your prefixes always be short and your results ever relevant!