Autocomplete System with Trie in DSA C++ - Build from Scratch

Autocomplete System with Trie

📖 Scenario: You are building a simple autocomplete system like the ones used in search engines or messaging apps. When a user types a few letters, the system suggests words that start with those letters.To do this efficiently, you will use a Trie data structure, which stores words in a tree-like form where each node represents a letter.

🎯 Goal: Build a Trie to store a list of words, then find and print all words that start with a given prefix.

📋 What You'll Learn

Create a Trie node structure with children and a flag for word end

Insert given words into the Trie

Search the Trie for all words starting with a given prefix

Print the list of autocomplete suggestions

💡 Why This Matters

🌍 Real World

Autocomplete systems help users type faster by suggesting words based on what they start typing, used in search engines, messaging apps, and code editors.

💼 Career

Understanding Tries and autocomplete logic is useful for software engineers working on search features, text input optimization, and user experience improvements.

1

Create Trie Node Structure

Define a struct called TrieNode with a boolean isEndOfWord initialized to false and an array of 26 TrieNode* pointers called children initialized to nullptr.

DSA C++

# Define the TrieNode struct with isEndOfWord and children array
# Your code here

Hint

Think of isEndOfWord as a flag to mark if a node completes a word. The children array holds pointers for each letter a-z.

2

Insert Words into Trie

Create a function called insertWord that takes a TrieNode* called root and a const std::string& word. Insert the word into the Trie by creating nodes for each letter if they don't exist and mark the last node's isEndOfWord as true.

DSA C++

struct TrieNode {
    bool isEndOfWord = false;
    TrieNode* children[26] = {nullptr};
};

// Write insertWord function below
// Your code here

Hint

Loop through each character, calculate its index by subtracting 'a', create a new node if needed, then move to that node. After the loop, mark the node as end of word.

3

Find Words Starting with Prefix

Write a function called findWordsWithPrefix that takes a TrieNode* called root, a const std::string& prefix, and a std::vector<std::string>& results. Traverse the Trie to the node matching the prefix, then collect all words starting from that node by DFS and add them to results.

DSA C++

struct TrieNode {
    bool isEndOfWord = false;
    TrieNode* children[26] = {nullptr};
};

void insertWord(TrieNode* root, const std::string& word) {
    TrieNode* current = root;
    for (char ch : word) {
        int index = ch - 'a';
        if (current->children[index] == nullptr) {
            current->children[index] = new TrieNode();
        }
        current = current->children[index];
    }
    current->isEndOfWord = true;
}

// Write findWordsWithPrefix function below
// Your code here

Hint

First, move down the Trie nodes matching the prefix. If any letter node is missing, return immediately. Then use a helper DFS function to find all words starting from that node.

4

Print Autocomplete Suggestions

In main(), create a TrieNode* called root. Insert these words: "apple", "app", "apricot", "banana". Then create a std::vector<std::string> called results. Call findWordsWithPrefix(root, "ap", results). Finally, print each word in results on its own line.

DSA C++

struct TrieNode {
    bool isEndOfWord = false;
    TrieNode* children[26] = {nullptr};
};

void insertWord(TrieNode* root, const std::string& word) {
    TrieNode* current = root;
    for (char ch : word) {
        int index = ch - 'a';
        if (current->children[index] == nullptr) {
            current->children[index] = new TrieNode();
        }
        current = current->children[index];
    }
    current->isEndOfWord = true;
}

void dfs(TrieNode* node, std::string currentWord, std::vector& results) {
    if (node->isEndOfWord) {
        results.push_back(currentWord);
    }
    for (int i = 0; i children[i] != nullptr) {
            dfs(node->children[i], currentWord + char('a' + i), results);
        }
    }
}

void findWordsWithPrefix(TrieNode* root, const std::string& prefix, std::vector& results) {
    TrieNode* current = root;
    for (char ch : prefix) {
        int index = ch - 'a';
        if (current->children[index] == nullptr) {
            return; // No words with this prefix
        }
        current = current->children[index];
    }
    dfs(current, prefix, results);
}

int main() {
    // Insert words and print autocomplete suggestions
    // Your code here
}

Hint

Insert the words into the Trie, then find all words starting with "ap" and print each on a new line.

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