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.

Practice

1. What is the main purpose of using a Trie in an autocomplete system?

easy

A. To efficiently store and search prefixes of words

B. To sort words alphabetically

C. To store words in a linked list

D. To perform arithmetic operations on words

Solution

1. Step 1: Understand the role of Trie in prefix search

   A Trie is a tree-like data structure that stores characters of words in a way that common prefixes share nodes.

2. Step 2: Connect Trie usage to autocomplete

   Autocomplete requires quick lookup of words starting with a given prefix, which Trie supports efficiently by traversing prefix nodes.

3. Final Answer:

   To efficiently store and search prefixes of words -> Option A

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie is all about prefix matching fast [OK]

Common Mistakes:

• Confusing Trie with sorting structures
• Thinking Trie stores words linearly
• Assuming Trie does arithmetic

2. Which of the following is the correct way to declare a Trie node class in C++?

easy

A. class TrieNode { public: map children; bool isEnd; };

B. class TrieNode { int children[26]; bool isEnd; };

C. class TrieNode { public: TrieNode* children[26]; bool isEnd; TrieNode() { for(int i=0; i<26; i++) children[i] = nullptr; isEnd = false; } };

D. struct TrieNode { vector<int> children; bool isEnd; };

Solution

1. Step 1: Check for pointer array initialization

   class TrieNode { public: TrieNode* children[26]; bool isEnd; TrieNode() { for(int i=0; i<26; i++) children[i] = nullptr; isEnd = false; } }; correctly declares an array of 26 pointers to TrieNode, initialized to nullptr, representing children for each alphabet letter.

2. Step 2: Verify isEnd boolean initialization

   class TrieNode { public: TrieNode* children[26]; bool isEnd; TrieNode() { for(int i=0; i<26; i++) children[i] = nullptr; isEnd = false; } }; sets isEnd to false in constructor, which marks if a word ends at this node.

3. Final Answer:

   class TrieNode { public: TrieNode* children[26]; bool isEnd; TrieNode() { for(int i=0; i<26; i++) children[i] = nullptr; isEnd = false; } }; -> Option C

4. Quick Check:

   Pointer array + bool flag = class TrieNode { public: TrieNode* children[26]; bool isEnd; TrieNode() { for(int i=0; i<26; i++) children[i] = nullptr; isEnd = false; } }; [OK]

Hint: Trie nodes use pointer arrays for children [OK]

Common Mistakes:

• Using int array instead of pointer array
• Not initializing children pointers
• Using map<int> instead of map<char>

3. What will be the output of the following C++ code snippet that inserts words into a Trie and searches for prefix "app"?

class TrieNode {
public:
    TrieNode* children[26];
    bool isEnd;
    TrieNode() {
        for(int i=0; i<26; i++) children[i] = nullptr;
        isEnd = false;
    }
};

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

    void insert(string word) {
        TrieNode* node = root;
        for(char c : word) {
            int idx = c - 'a';
            if(!node->children[idx])
                node->children[idx] = new TrieNode();
            node = node->children[idx];
        }
        node->isEnd = true;
    }

    bool startsWith(string prefix) {
        TrieNode* node = root;
        for(char c : prefix) {
            int idx = c - 'a';
            if(!node->children[idx]) return false;
            node = node->children[idx];
        }
        return true;
    }
};

int main() {
    Trie trie;
    trie.insert("apple");
    trie.insert("app");
    cout << (trie.startsWith("app") ? "Yes" : "No") << endl;
    cout << (trie.startsWith("apl") ? "Yes" : "No") << endl;
    return 0;
}

medium

A. No
Yes

B. Yes
No

C. Yes
Yes

D. No
No

Solution

1. Step 1: Insert words "apple" and "app" into Trie

   Both words share prefix "app", so nodes for 'a', 'p', 'p' exist. "apple" adds nodes for 'l' and 'e'.

2. Step 2: Check startsWith for "app" and "apl"

   "app" prefix exists, so returns true (prints "Yes"). "apl" prefix does not exist (no 'l' after 'p'), so returns false (prints "No").

3. Final Answer:

   Yes No -> Option B

4. Quick Check:

   Prefix "app" found, "apl" not found = Yes No [OK]

Hint: Check prefix nodes existence for startsWith [OK]

Common Mistakes:

• Confusing isEnd with prefix existence
• Assuming "apl" is found because 'a' and 'p' exist
• Printing boolean instead of Yes/No

4. Identify the bug in this Trie insertion code snippet:

void insert(string word) {
    TrieNode* node = root;
    for(char c : word) {
        int idx = c - 'a';
        if(node->children[idx] == nullptr)
            node->children[idx] = new TrieNode();
        node = node->children[idx];
        node->isEnd = true;
    }
}

medium

A. Setting isEnd = true inside the loop causes all prefixes to be marked as words

B. Not initializing children array to nullptr

C. Missing root initialization

D. Incorrect index calculation for children array

Solution

1. Step 1: Analyze isEnd assignment inside loop

   Setting isEnd = true inside the loop marks every node along the word as an end of a word, incorrectly marking prefixes as complete words.

2. Step 2: Correct placement of isEnd assignment

   isEnd should be set to true only after the loop ends, marking only the last node as end of the inserted word.

3. Final Answer:

   Setting isEnd = true inside the loop causes all prefixes to be marked as words -> Option A

4. Quick Check:

   isEnd inside loop = wrong word marking [OK]

Hint: Set isEnd true only after full word insertion [OK]

Common Mistakes:

• Marking prefixes as complete words
• Forgetting to set isEnd at all
• Incorrect children pointer checks

5. You want to implement an autocomplete system that returns all words starting with a given prefix using a Trie. Which approach correctly retrieves all such words?

hard

A. Use a hash map to store prefix to word list mapping directly

B. Store all words in a vector and filter by prefix each time

C. Traverse Trie and return words only if isEnd is true at prefix node

D. Traverse Trie to prefix node, then perform DFS to collect all words below it

Solution

1. Step 1: Locate prefix node in Trie

   Traverse the Trie character by character to reach the node representing the last character of the prefix.

2. Step 2: Perform DFS from prefix node to collect words

   From this node, recursively explore all child nodes to find all words that start with the prefix, collecting those where isEnd is true.

3. Final Answer:

   Traverse Trie to prefix node, then perform DFS to collect all words below it -> Option D

4. Quick Check:

   Prefix node + DFS = all autocomplete words [OK]

Hint: Find prefix node, then DFS to get all words [OK]

Common Mistakes:

• Returning only prefix node word ignoring children
• Filtering all words each query (inefficient)
• Using hash map without Trie traversal