Course contentsShow
← Computer Science
Lesson 628 of 2,87215. Tries and Specialized TreesFree lesson

Autocomplete with Tries

Building autocomplete functionality by finding all words that share a common prefix using trie traversal.

What You'll Learn

You'll learn how to build autocomplete functionality by finding all words that share a common prefix using trie traversal techniques.

The Autocomplete Problem

When you type "cat" into a search box and see suggestions like "cat," "catch," "category," and "cathedral," you're experiencing autocomplete. This feature requires quickly finding all words that start with a given prefix—a perfect job for tries.

How It Works

Autocomplete with tries is a two-step process:

Step 1: Navigate to the Prefix
First, traverse the trie following the characters of your prefix. For prefix "cat," you'd move through nodes c → a → t. If you can't complete this path, the prefix doesn't exist, and there are no suggestions.

Step 2: Collect All Words Below
Once you reach the prefix's last character node, perform a depth-first traversal of the entire subtree beneath it. Every node marked as "end of word" represents a valid completion. As you traverse, build up the word by tracking the path of characters.

The Algorithm Pattern

function autocomplete(prefix):
    node = navigateToPrefix(prefix)
    if node is null:
        return empty list
    
    results = []
    collectWords(node, prefix, results)
    return results

function collectWords(node, currentWord, results):
    if node.isEndOfWord:
        results.add(currentWord)
    
    for each child in node.children:
        collectWords(child, currentWord + child.character, results)

Practical Considerations

The navigation step takes O(p) time where p is the prefix length. Collecting k results from a subtree containing n total characters takes O(n) time in the worst case, though you can optimize by limiting results.

Key Takeaway: Autocomplete with tries works by navigating to the prefix node, then recursively traversing its subtree to collect all complete words—efficiently turning partial input into useful suggestions.