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.