Trie Applications: Autocomplete, Spell-Check & Word Search

The trie’s superpower is prefix queries, and that single ability underpins a surprising number of real systems: autocomplete, spell-checkers, and word-search solvers. This page walks through each application and then builds the canonical one — collecting every word that starts with a given prefix, the engine behind type-ahead suggestions. It builds directly on the trie operations.

Autocomplete (type-ahead suggestions)

When you type app into a search box and see apple, application, apply, that is a trie at work. The system walks to the app node in O(L) and then gathers every complete word in the subtree beneath it. Because the prefix is matched once and suggestions live in a shared subtree, this is far cheaper than scanning the whole dictionary.

Spell-check

A spell-checker stores a dictionary in a trie and checks each typed word with search in O(L). For suggestions on a misspelling, it explores nearby tries paths — for example, walking the trie while allowing a small number of character edits (insert/delete/substitute), a trie-guided version of edit distance. The trie prunes huge swaths of impossible words early because a wrong prefix has no subtree to explore.

Word search and prefix matching

In a Boggle-style word grid, you store the dictionary in a trie and run DFS from each cell. At every step you check startsWith on the path built so far; the moment the current prefix is absent from the trie, you prune that branch entirely. Tries also drive longest-prefix matching in IP routing tables and URL routers.

Going deeper: The pruning is what makes trie + DFS fast. Without the trie you would test every grid path against the whole dictionary; with it, a dead prefix kills the search instantly.

Building autocomplete: collect all words with a prefix

Here is the core routine. Walk to the prefix node, then do a depth-first traversal of its subtree, rebuilding each full word and collecting the ones marked isEnd. This assumes the TrieNode, root, and the findNode helper from earlier pages.

void collect(TrieNode* node, std::string& path, std::vector<std::string>& out) {
    if (node->isEnd) out.push_back(path);
    for (auto& [ch, child] : node->children) {
        path.push_back(ch);
        collect(child, path, out);
        path.pop_back();          // backtrack
    }
}

std::vector<std::string> autocomplete(const std::string& prefix) {
    std::vector<std::string> out;
    TrieNode* node = findNode(prefix);   // walk to the prefix node
    if (!node) return out;               // no word has this prefix
    std::string path = prefix;
    collect(node, path, out);
    return out;
}

private void collect(TrieNode node, StringBuilder path, List<String> out) {
    if (node.isEnd) out.add(path.toString());
    for (Map.Entry<Character, TrieNode> e : node.children.entrySet()) {
        path.append(e.getKey());
        collect(e.getValue(), path, out);
        path.deleteCharAt(path.length() - 1);   // backtrack
    }
}

public List<String> autocomplete(String prefix) {
    List<String> out = new ArrayList<>();
    TrieNode node = findNode(prefix);    // walk to the prefix node
    if (node == null) return out;        // no word has this prefix
    collect(node, new StringBuilder(prefix), out);
    return out;
}

collect(node, path, out) {
  if (node.isEnd) out.push(path);
  for (const [ch, child] of node.children) {
    this.collect(child, path + ch, out);
  }
}

autocomplete(prefix) {
  const out = [];
  const node = this.findNode(prefix);   // walk to the prefix node
  if (node === null) return out;        // no word has this prefix
  this.collect(node, prefix, out);
  return out;
}

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

def autocomplete(self, prefix):
    out = []
    node = self._find_node(prefix)       # walk to the prefix node
    if node is None:                     # no word has this prefix
        return out
    self._collect(node, prefix, out)
    return out

Complexity: O(L + k) time, where L is the prefix length and k is the total size of the matched subtree (proportional to the number and length of matching words). That is dramatically better than the O(n · L) of scanning every stored word in a hash set.

For beginners: The collect routine is plain recursion with backtracking: go down a branch building the word, record it if it ends a word, then undo the last character before trying the next branch. The C++ and Java versions mutate one shared buffer and undo it; the JS and Python versions pass a fresh string down — both are correct.

Ranking suggestions

Real autocomplete ranks results — most-searched first. Two common upgrades:

• Store a frequency or score at each end node, then sort the collected words by it.
• Keep a small top-k list and stop early once you have enough high-scoring matches.

These are layered on top of the same prefix-collection skeleton.

When a trie is the right tool

Choose a trie for these applications when you need fast, repeated prefix queries over a large, mostly static set of strings. For one-off exact lookups, a hash set is simpler. For ranked search at massive scale, production systems combine tries with extra indexing — but the trie remains the prefix engine at the core.

Ready to build these yourself? Try the trie exercises, or see the full text autocomplete project.