Autocomplete System with Trie in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Trie Insert and Search

What is the output of the following C++ code that inserts words into a Trie and searches for a prefix?

DSA C++

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

struct TrieNode {
    TrieNode* children[26] = {nullptr};
    bool 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") << endl;
    cout << trie.startsWith("apl") << endl;
    return 0;
}

A

1
0

B

0
1

C

1
1

D

0
0

💡 Hint

Check if the prefix exists in the Trie after inserting the words.

The prefix "app" exists because both "app" and "apple" were inserted, so startsWith("app") returns true (1). The prefix "apl" does not exist, so startsWith("apl") returns false (0).

🧠 Conceptual

intermediate

Understanding Trie Node Structure

Which of the following best describes the purpose of the 'isEnd' boolean in a Trie node?

A It counts how many words pass through this node.

B It marks the node as the end of a valid word stored in the Trie.

C It stores the character value of the node.

D It indicates if the node has any children nodes.

💡 Hint

Think about how the Trie knows when a word finishes.

The 'isEnd' boolean marks that the path from root to this node forms a complete valid word in the Trie.

🔧 Debug

advanced

Identify the Bug in Trie Search

What error will occur when running this code snippet for searching a word in a Trie?

DSA C++

bool search(string word) {
    TrieNode* node = root;
    for (char c : word) {
        int idx = c - 'a';
        if (node->children[idx] == nullptr)
            return false;
        node = node->children[idx];
    }
    return node->isEnd;
}

// root is not initialized in constructor

A Returns false always

B Runs correctly and returns true or false

C Compilation error due to missing return statement

D Segmentation fault due to uninitialized root pointer

💡 Hint

Check if root pointer is properly set before use.

If root is not initialized (e.g., root = new TrieNode()), accessing root->children causes a segmentation fault (crash).

🚀 Application

advanced

Autocomplete Suggestions Using Trie

Given a Trie with words inserted, which approach correctly collects all words starting with a given prefix?

A Store all words in a list and search prefix using string matching

B Check all nodes in Trie and filter words starting with prefix

C Traverse to prefix node, then DFS to collect all words from there

D Use BFS from root to find prefix and return first matching word only

💡 Hint

Think about efficient traversal after locating prefix node.

After reaching the node representing the prefix, a depth-first search (DFS) collects all words below it efficiently.

❓ Predict Output

expert

Output of Trie Autocomplete Function

What is the output of this C++ code that inserts words and prints autocomplete suggestions for prefix "ca"?

DSA C++

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

struct TrieNode {
    TrieNode* children[26] = {nullptr};
    bool 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;
    }

    void dfs(TrieNode* node, string prefix, vector<string>& results) {
        if (node->isEnd) results.push_back(prefix);
        for (int i = 0; i < 26; i++) {
            if (node->children[i]) {
                dfs(node->children[i], prefix + char('a' + i), results);
            }
        }
    }

    vector<string> autocomplete(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (!node->children[idx]) return {};
            node = node->children[idx];
        }
        vector<string> results;
        dfs(node, prefix, results);
        return results;
    }
};

int main() {
    Trie trie;
    trie.insert("cat");
    trie.insert("car");
    trie.insert("cart");
    trie.insert("dog");
    vector<string> res = trie.autocomplete("ca");
    for (string s : res) cout << s << " ";
    return 0;
}

A car cart cat

B cart car cat

C cat car cart

D dog

💡 Hint

Check the order of DFS traversal over children nodes.

DFS visits children in alphabetical order (a to z). From prefix "ca", the node has children 'r' (index 17) and 't' (index 19). The loop processes 'r' first, collecting "car" and "cart", then 't', collecting "cat". Thus, the order is "car", "cart", "cat".