Trie Search Operation in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Trie Search for Existing Word

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

DSA C++

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

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool isEndOfWord = false;
};

class Trie {
public:
    TrieNode* root;
    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 search(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            if (!node->children.count(c)) return false;
            node = node->children[c];
        }
        return node->isEndOfWord;
    }
};

int main() {
    Trie trie;
    trie.insert("cat");
    trie.insert("car");
    trie.insert("dog");
    cout << (trie.search("cat") ? "Found" : "Not Found") << endl;
    return 0;
}

A Runtime Error

B Not Found

C Compilation Error

D Found

💡 Hint

Check if the search function correctly identifies the end of the word.

The word "cat" was inserted into the Trie, so searching for it returns true and prints "Found".

❓ Predict Output

intermediate

Output of Trie Search for Non-Existing Word

What will be printed when searching for the word "cap" in the Trie after inserting "cat", "car", and "dog"?

DSA C++

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

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool isEndOfWord = false;
};

class Trie {
public:
    TrieNode* root;
    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 search(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            if (!node->children.count(c)) return false;
            node = node->children[c];
        }
        return node->isEndOfWord;
    }
};

int main() {
    Trie trie;
    trie.insert("cat");
    trie.insert("car");
    trie.insert("dog");
    cout << (trie.search("cap") ? "Found" : "Not Found") << endl;
    return 0;
}

A Not Found

B Found

C Compilation Error

D Runtime Error

💡 Hint

Check if the search function returns false when the word is not fully present.

The word "cap" was not inserted, so the search returns false and prints "Not Found".

🧠 Conceptual

advanced

Understanding Trie Search Behavior with Prefixes

If the Trie contains the words "bat" and "bath", what will the search function return when searching for "bat" and "bath" respectively?

A "bat" returns true, "bath" returns false

B "bat" returns true, "bath" returns true

C "bat" returns false, "bath" returns true

D "bat" returns false, "bath" returns false

💡 Hint

Remember that search returns true only if the word ends at a node marked as end of word.

Both "bat" and "bath" were inserted, so searching for either returns true.

🔧 Debug

advanced

Identify the Error in Trie Search Implementation

What error will occur when running this Trie search code snippet?

DSA C++

bool search(const string& word) {
    TrieNode* node = root;
    for (char c : word) {
        if (node->children[c] == nullptr) return false;
        node = node->children[c];
    }
    return node->isEndOfWord;
}

A Runtime Error due to accessing non-existing key in unordered_map

B Returns false always

C Compilation Error due to missing return statement

D Works correctly without error

💡 Hint

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

Using operator[] on unordered_map with a missing key inserts a new key with default value, so checking == nullptr is invalid and can cause logic errors or runtime issues.

🚀 Application

expert

Number of Words in Trie After Insertions

After inserting the words "apple", "app", "application", "bat", and "bath" into an empty Trie, how many words will the Trie contain?

A 3

B 4

C 5

D 6

💡 Hint

Each inserted word counts as one word regardless of prefix sharing.

All five words are distinct and inserted, so the Trie contains 5 words.