Prefix Search Using 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 <unordered_map>
#include <string>
using namespace std;

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

class Trie {
private:
    TrieNode* root;
public:
    Trie() { root = new TrieNode(); }
    void insert(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            if (!node->children.count(c)) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->isEndOfWord = true;
    }
    bool startsWith(const string& prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            if (!node->children.count(c)) return false;
            node = node->children[c];
        }
        return true;
    }
};

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

A

true
true

B

true
false

C

false
false

D

false
true

💡 Hint

Think about whether the prefix "app" and "apl" exist in the inserted words.

The prefix "app" exists because both "apple" and "app" start with "app".

The prefix "apl" does not exist in the Trie because no inserted word starts with "apl".

🧠 Conceptual

intermediate

Number of Nodes in Trie After Insertions

If you insert the words ["cat", "car", "cart"] into an empty Trie, how many nodes will the Trie contain (including the root)?

A 10

B 8

C 9

D 7

💡 Hint

Count shared prefixes carefully to avoid double counting nodes.

Root node counts as 1.

Words share prefixes: "cat", "car", "cart" share 'c' and 'a' and 'r' nodes.

Counting nodes: root(1), c(2), a(3), t(4), r(5), t(6).

🔧 Debug

advanced

Identify the Error in Trie Search Function

What error will the following C++ Trie search function cause when searching for a prefix that does not exist?

DSA C++

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

A Runtime error: accessing non-existent key in unordered_map

B Returns false correctly without error

C Compilation error due to missing return statement

D Always returns true regardless of prefix

💡 Hint

Check how unordered_map operator[] behaves when key is missing.

Using operator[] on unordered_map with a missing key inserts a new node, so node is never null.

Then dereferencing node->children[c] when node is null causes runtime error.

🚀 Application

advanced

Find All Words With Given Prefix

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

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

B Check each word in the Trie root's children for prefix match

C Store all words in a list and filter by prefix each time

D Use BFS from root and stop at first prefix match

💡 Hint

Think about efficient traversal starting from the prefix node.

Option A is correct because it efficiently finds the prefix node and explores all descendants.

Other options are inefficient or incorrect.

❓ Predict Output

expert

Output of Trie Prefix Search with Multiple Insertions

What is the output of the following C++ code that inserts multiple words and checks prefixes?

DSA C++

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

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

class Trie {
private:
    TrieNode* root;
    void dfs(TrieNode* node, string current, vector<string>& results) {
        if (node->isEndOfWord) results.push_back(current);
        for (auto& pair : node->children) {
            dfs(pair.second, current + pair.first, results);
        }
    }
public:
    Trie() { root = new TrieNode(); }
    void insert(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            if (!node->children.count(c)) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->isEndOfWord = true;
    }
    vector<string> findWordsWithPrefix(const string& prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            if (!node->children.count(c)) return {};
            node = node->children[c];
        }
        vector<string> results;
        dfs(node, prefix, results);
        return results;
    }
};

int main() {
    Trie trie;
    trie.insert("test");
    trie.insert("team");
    trie.insert("teach");
    trie.insert("toast");
    vector<string> words = trie.findWordsWithPrefix("te");
    for (const string& w : words) {
        cout << w << " ";
    }
    cout << endl;
    return 0;
}

A test teach team

B teach team test

C team teach test

D test team teach

💡 Hint

The DFS visits children in order of insertion in unordered_map, which is not ordered, but assume insertion order for this question.

The DFS visits children in the order they were inserted: 's' for test, 'a' for team and teach.

So words collected are "test", "team", "teach" in that order.

Practice

1. What is the main purpose of using a Trie data structure in prefix search?

easy

A. To reverse strings quickly

B. To sort words alphabetically

C. To store words in a hash table

D. To efficiently find all words that start with a given prefix

Solution

1. Step 1: Understand Trie usage

   A Trie stores characters of words in a tree structure, allowing quick prefix lookups.

2. Step 2: Identify prefix search goal

   Prefix search means finding all words starting with a given prefix efficiently, which Trie supports well.

3. Final Answer:

   To efficiently find all words that start with a given prefix -> Option D

4. Quick Check:

   Trie = Prefix search efficiency [OK]

Hint: Trie is built for prefix-based fast searches [OK]

Common Mistakes:

• Confusing Trie with sorting algorithms
• Thinking Trie is a hash table
• Assuming Trie reverses strings

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

easy

A. struct TrieNode { bool isEnd; TrieNode* children[26]; };

B. struct TrieNode { int value; TrieNode children; };

C. class TrieNode { bool isEnd; vector<int> children; };

D. struct TrieNode { bool isEnd; TrieNode children[]; };

Solution

1. Step 1: Check Trie node structure

   A Trie node typically has a boolean to mark word end and an array of pointers for children nodes.

2. Step 2: Match correct syntax

   struct TrieNode { bool isEnd; TrieNode* children[26]; }; correctly declares a boolean and an array of 26 pointers for English lowercase letters.

3. Final Answer:

   struct TrieNode { bool isEnd; TrieNode* children[26]; }; -> Option A

4. Quick Check:

   Trie node = bool + pointer array [OK]

Hint: Trie nodes have boolean + fixed-size pointer array [OK]

Common Mistakes:

• Using vector<int> instead of pointers
• Missing pointer (*) in children array
• Declaring children as single object, not array

3. Given the following code snippet, what will be the output after inserting words "cat", "car", "dog" and searching prefix "ca"?

Trie trie;
trie.insert("cat");
trie.insert("car");
trie.insert("dog");
vector<string> result = trie.searchPrefix("ca");
for (auto &word : result) std::cout << word << " ";

medium

A. cat car

B. dog

C. cat dog car

D. car cat dog

Solution

1. Step 1: Insert words into Trie

   Words "cat", "car", and "dog" are inserted. Trie stores them by characters.

2. Step 2: Search prefix "ca"

   Searching prefix "ca" returns all words starting with "ca", which are "cat" and "car".

3. Final Answer:

   cat car -> Option A

4. Quick Check:

   Prefix "ca" matches "cat" and "car" [OK]

Hint: Search returns words starting exactly with prefix [OK]

Common Mistakes:

• Including words without the prefix
• Assuming order is alphabetical by default
• Confusing prefix search with full word search

4. Identify the bug in this Trie insert function snippet:

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

medium

A. Children array should be vector, not array

B. isEnd should be set to true after insertion

C. Index calculation is incorrect

D. Root node is not initialized

Solution

1. Step 1: Review isEnd assignment

   After inserting a word, the node representing last character should mark end of word by setting isEnd to true.

2. Step 2: Identify incorrect isEnd value

   Code sets isEnd to false, which is wrong and will cause search failures.

3. Final Answer:

   isEnd should be set to true after insertion -> Option B

4. Quick Check:

   Mark word end with isEnd = true [OK]

Hint: Set isEnd true at word end to mark complete word [OK]

Common Mistakes:

• Setting isEnd to false instead of true
• Forgetting to initialize root node
• Miscomputing index from character

5. You want to find all words in a Trie that start with prefix "app" and have length exactly 5. Which approach correctly applies prefix search with length filtering?

hard

A. Use a hash map instead of Trie for prefix and length search

B. Search prefix "app" and return all words regardless of length

C. Search prefix "app" in Trie, then collect words with length 5 only

D. Search all words and filter those starting with "app" and length 5

Solution

1. Step 1: Perform prefix search "app" in Trie

   Traverse Trie nodes for prefix "app" to reach subtree containing all matching words.

2. Step 2: Filter collected words by length 5

   From subtree, collect only words whose length equals 5 to meet the length condition.

3. Final Answer:

   Search prefix "app" in Trie, then collect words with length 5 only -> Option C

4. Quick Check:

   Prefix search + length filter = Search prefix "app" in Trie, then collect words with length 5 only [OK]

Hint: Filter length after prefix search for efficient results [OK]

Common Mistakes:

• Returning all prefix matches without length check
• Filtering all words instead of prefix subtree
• Using hash map losing prefix search efficiency