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.