Autocomplete with Tries

Extend a trie to collect every word that shares a given prefix using a DFS suffix walk, then cap results to the top-k suggestions for a real autocomplete API.

5 min read Level 3/5 #dsa#trie#autocomplete

What you'll learn

Implement a DFS suffix collector that gathers all words below a trie node
Return the top-k completions for a given prefix
Understand the time cost of suggestion collection relative to result count

Once you can reach a node by traversing a prefix, every word stored in the subtree rooted at that node is a valid completion. A depth-first walk collects them all; an optional limit keeps the response size bounded.

Collecting All Completions

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

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char);
    }
    node.isEnd = true;
  }

  /**
   * Return all words that start with prefix.
   * O(m + S) where m = prefix length, S = total characters in matching words.
   */
  autocomplete(prefix) {
    const start = this._traverse(prefix);
    if (start === null) return [];

    const results = [];
    this._collect(start, prefix, results);
    return results;
  }

  _collect(node, current, results) {
    if (node.isEnd) results.push(current);

    for (const [char, child] of node.children) {
      this._collect(child, current + char, results);
    }
  }

  _traverse(s) {
    let node = this.root;
    for (const char of s) {
      if (!node.children.has(char)) return null;
      node = node.children.get(char);
    }
    return node;
  }
}

_collect carries the path string built so far (current) and appends it to results whenever it lands on a node where isEnd is true.

Limiting to Top-k Suggestions

For a real autocomplete API you rarely want more than 10 results. Pass a limit and stop the DFS early:

_collect(node, current, results, limit) {
  if (results.length >= limit) return;
  if (node.isEnd) results.push(current);

  for (const [char, child] of node.children) {
    if (results.length >= limit) break;
    this._collect(child, current + char, results, limit);
  }
}

autocomplete(prefix, limit = 10) {
  const start = this._traverse(prefix);
  if (start === null) return [];
  const results = [];
  this._collect(start, prefix, results, limit);
  return results;
}

The early exit means the DFS terminates as soon as k words are found, so the effective cost is O(m + k · avg_word_length) instead of O(m + S).

Worked Example

const trie = new Trie();
["apple", "app", "application", "apply", "apt", "banana"].forEach(w =>
  trie.insert(w)
);

trie.autocomplete("app");
// ["app", "apple", "application", "apply"]

trie.autocomplete("app", 2);
// ["app", "apple"]

trie.autocomplete("ban");
// ["banana"]

trie.autocomplete("xyz");
// []

Complexity

Operation	Time	Notes
autocomplete(prefix)	O(m + S)	S = chars in all matching words
autocomplete(prefix, k)	O(m + k · L)	L = average matching word length
Insert	O(m)	unchanged from base trie

Frequency-Ranked Suggestions

Production autocomplete systems rank by query frequency. Store a count alongside isEnd on each node, increment it on every insert, and sort the collected results by count before returning. The trie structure stays the same; only the aggregation step changes.

Up Next

Apply the trie’s prefix-pruning power to a 2D word-search board, cutting off dead branches before they are fully explored.

Word Search on a Board →