Autocomplete System with Trie in DSA C++

Mental Model

A trie stores words by sharing common prefixes, so we can quickly find all words starting with a given prefix.

Analogy: Imagine a tree of roads where each road sign is a letter. To find all shops starting with 'ca', you follow the roads labeled 'c' then 'a' and see all shops branching from there.

root
 ↓
 c -> a -> t -> [end]
       ↓
       r -> [end]
       ↓
       p -> [end]

Dry Run Walkthrough

Input: words: ["cat", "car", "cap"], prefix: "ca"

Goal: Find all words starting with prefix "ca"

Step 1: Insert word "cat" into trie

root -> c -> a -> t -> [end]

Why: Add each letter as a node, marking the end of the word

Step 2: Insert word "car" sharing prefix "ca"

root -> c -> a -> t -> [end]
               ↓
               r -> [end]

Why: Reuse existing nodes for 'c' and 'a', add new node 'r'

Step 3: Insert word "cap" sharing prefix "ca"

root -> c -> a -> t -> [end]
               ↓
               r -> [end]
               ↓
               p -> [end]

Why: Add new node 'p' after 'a' sharing prefix

Step 4: Search for prefix "ca"

At node 'a' after root -> c -> a

Why: Traverse trie nodes matching prefix letters

Step 5: Collect all words starting from node 'a'

Found words: "cat", "car", "cap"

Why: Explore all branches from prefix node to get completions

Result:

root -> c -> a -> t -> [end]
               ↓
               r -> [end]
               ↓
               p -> [end]
Autocomplete results: ["cat", "car", "cap"]

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isEndOfWord = false;
};

class Trie {
private:
    TrieNode* root;

    void dfs(TrieNode* node, string prefix, vector<string>& results) {
        if (node->isEndOfWord) {
            results.push_back(prefix);
        }
        for (auto& child : node->children) {
            dfs(child.second, prefix + child.first, results); // explore deeper
        }
    }

public:
    Trie() {
        root = new TrieNode();
    }

    void insert(const string& word) {
        TrieNode* curr = root;
        for (char c : word) {
            if (curr->children.find(c) == curr->children.end()) {
                curr->children[c] = new TrieNode(); // create node if missing
            }
            curr = curr->children[c]; // move to next node
        }
        curr->isEndOfWord = true; // mark word end
    }

    vector<string> autocomplete(const string& prefix) {
        TrieNode* curr = root;
        for (char c : prefix) {
            if (curr->children.find(c) == curr->children.end()) {
                return {}; // prefix not found
            }
            curr = curr->children[c]; // move to prefix node
        }
        vector<string> results;
        dfs(curr, prefix, results); // collect all words
        return results;
    }
};

int main() {
    Trie trie;
    vector<string> words = {"cat", "car", "cap"};
    for (const string& w : words) {
        trie.insert(w);
    }
    string prefix = "ca";
    vector<string> results = trie.autocomplete(prefix);
    for (const string& word : results) {
        cout << word << "\n";
    }
    return 0;
}

if (curr->children.find(c) == curr->children.end()) { curr->children[c] = new TrieNode(); // create node if missing }

create new node only if letter path does not exist to share prefixes

curr = curr->children[c]; // move to next node

advance current pointer to next letter node

curr->isEndOfWord = true; // mark word end

mark node as end of a valid word

if (curr->children.find(c) == curr->children.end()) { return {}; // prefix not found }

stop search early if prefix path missing

dfs(curr, prefix, results); // collect all words

explore all descendant nodes to find completions

Output

cat

car

cap

Complexity Analysis

Time: O(m + k) where m is prefix length and k is total letters in matched words because we traverse prefix then collect all completions

Space: O(n * l) where n is number of words and l is average length due to trie nodes storing letters

vs Alternative: Compared to scanning all words for prefix (O(n*l)), trie reduces prefix search to O(m) plus output size, making autocomplete efficient

Edge Cases

Empty prefix string

Returns all words in trie as completions

DSA C++

for (char c : prefix) {
    if (curr->children.find(c) == curr->children.end()) {
        return {}; // prefix not found
    }
    curr = curr->children[c];
}

Prefix not present in trie

Returns empty list immediately

DSA C++

if (curr->children.find(c) == curr->children.end()) {
    return {}; // prefix not found
}

Words with shared prefixes

Trie nodes are shared, saving space and enabling fast prefix search

DSA C++

if (curr->children.find(c) == curr->children.end()) {
    curr->children[c] = new TrieNode();
}

When to Use This Pattern

When you need to find all words starting with a prefix quickly, use a trie because it stores words by shared prefixes enabling fast lookup and retrieval.

Common Mistakes

Mistake: Not marking the end of word node, causing autocomplete to return incomplete results
Fix: Set isEndOfWord = true at the last node of each inserted word

Mistake: Not checking if prefix path exists before searching deeper
Fix: Return empty result immediately if prefix letter node is missing

Summary

Stores words in a prefix tree to quickly find all words starting with a given prefix.

Use when implementing autocomplete or prefix-based search features.

The key is sharing nodes for common prefixes to avoid repeated work and speed up search.