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.

Practice

1. What does the search operation in a Trie data structure do?

easy

A. Checks if a given word exists in the Trie

B. Deletes a word from the Trie

C. Inserts a new word into the Trie

D. Counts the total words stored in the Trie

Solution

1. Step 1: Understand the purpose of search in Trie

   The search operation is designed to check if a specific word is present in the Trie structure.

2. Step 2: Differentiate from other operations

   Insertion adds words, deletion removes words, and counting totals words. Search only checks existence.

3. Final Answer:

   Checks if a given word exists in the Trie -> Option A

4. Quick Check:

   Trie search = check word presence [OK]

Hint: Search checks presence of word, not insertion or deletion [OK]

Common Mistakes:

• Confusing search with insert operation
• Thinking search deletes words
• Assuming search counts words

2. Which of the following is the correct way to check if a character node exists in a Trie during search in C++?

easy

A. if (node->children[ch])

B. if (node->children[ch] == nullptr)

C. if (node->children[ch] != nullptr)

D. if (node->children.find(ch) != node->children.end())

Solution

1. Step 1: Understand Trie children representation

   Trie children are usually stored in a map or unordered_map. To check existence, use find() method.

2. Step 2: Identify correct syntax for existence check

   Using find(ch) != end() confirms if character node exists without creating new nodes.

3. Final Answer:

   if (node->children.find(ch) != node->children.end()) -> Option D

4. Quick Check:

   Use find() to check key existence in map [OK]

Hint: Use find() != end() to check map key existence safely [OK]

Common Mistakes:

• Using node->children[ch] != nullptr causes insertion
• Accessing children[ch] directly creates new node
• Checking children[ch] == nullptr can cause insertion

3. Consider the following C++ Trie search code snippet:

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

What will be the output of search(root, "cat") if the Trie contains words: "car", "cat", "cap"?

medium

A. true

B. false

C. Compilation error

D. Runtime error

Solution

1. Step 1: Trace search for "cat" in Trie

   Each character 'c', 'a', 't' is found in children nodes. The loop completes without returning false.

2. Step 2: Check isEndOfWord flag at last node

   Since "cat" is inserted, the last node's isEndOfWord is true, so function returns true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Word "cat" exists in Trie = true [OK]

Hint: If all chars found and isEndOfWord true, search returns true [OK]

Common Mistakes:

• Ignoring isEndOfWord flag and returning true prematurely
• Assuming partial match means word exists
• Confusing false return with missing character

4. Identify the bug in the following Trie search function:

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

medium

A. Missing check for empty word input

B. Using node->children[ch] in if condition inserts new nodes unintentionally

C. Incorrect return type for search function

D. Loop variable should be int, not char

Solution

1. Step 1: Analyze children access in if condition

   Accessing node->children[ch] creates a new node if it doesn't exist, which is wrong during search.

2. Step 2: Correct way to check existence

   Use find() method to check if child exists without creating new nodes.

3. Final Answer:

   Using node->children[ch] in if condition inserts new nodes unintentionally -> Option B

4. Quick Check:

   Accessing map key directly creates nodes [OK]

Hint: Use find() to check existence, not direct map access [OK]

Common Mistakes:

• Using direct map access in condition causing side effects
• Ignoring empty string edge case
• Wrong loop variable type

5. You have a Trie storing the words: "apple", "app", "application", "bat", "batch". Which of the following search queries will return false?

hard

A. "batch"

B. "app"

C. "appl"

D. "bat"

Solution

1. Step 1: Check if "appl" is a complete word in Trie

   "appl" is a prefix of "apple" and "application" but not a complete word, so isEndOfWord is false.

2. Step 2: Verify other words

   "app", "batch", and "bat" are all complete words stored in the Trie, so search returns true for them.

3. Final Answer:

   "appl" -> Option C

4. Quick Check:

   Prefix only, not full word = false [OK]

Hint: Search returns false for prefixes not marked as words [OK]

Common Mistakes:

• Assuming prefix is always found as word
• Ignoring isEndOfWord flag
• Confusing similar words with exact matches