Word Search in 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 specific words?

DSA C++

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

struct TrieNode {
    TrieNode* children[26];
    bool isEndOfWord;
    TrieNode() {
        for (int i = 0; i < 26; i++) children[i] = nullptr;
        isEndOfWord = false;
    }
};

class Trie {
public:
    TrieNode* root;
    Trie() { root = new TrieNode(); }

    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->isEndOfWord = true;
    }

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

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

A

true
true
false

B

true
false
false

C

false
true
false

D

false
false
false

💡 Hint

Remember that search returns true only if the word is fully present and marked as end of word.

The words "app" and "apple" are inserted. Searching "app" and "apple" returns true because both are inserted as complete words. Searching "ap" returns false because it is a prefix but not a complete word in the Trie.

🧠 Conceptual

intermediate

Trie Node Children Count

In a Trie node, what does the number of non-null children pointers represent?

A The depth of the node in the Trie

B The number of words that end at this node

C The total number of words stored in the Trie

D The number of possible next characters from this node

💡 Hint

Think about what children pointers represent in a tree structure.

Each non-null child pointer corresponds to a possible next character that can follow the current prefix represented by the node.

🔧 Debug

advanced

Identify the Bug in Trie Search

What error will the following code produce when searching for a word not present in the Trie?

DSA C++

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

struct TrieNode {
    TrieNode* children[26];
    bool isEndOfWord;
    TrieNode() {
        for (int i = 0; i < 26; i++) children[i] = nullptr;
        isEndOfWord = false;
    }
};

class Trie {
public:
    TrieNode* root;
    Trie() { root = new TrieNode(); }

    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->isEndOfWord = true;
    }

    bool search(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            node = node->children[index];
        }
        return node->isEndOfWord;
    }
};

int main() {
    Trie trie;
    trie.insert("cat");
    cout << boolalpha << trie.search("car") << endl;
    return 0;
}

A Compilation error due to missing return

B Returns false

C Segmentation fault (runtime error)

D Returns true incorrectly

💡 Hint

Check what happens if a child pointer is null and you try to access it.

The search function does not check if the child pointer is null before moving to it. For "car", the 'r' child pointer is null, so accessing it causes a segmentation fault.

🚀 Application

advanced

Words Found in a Trie After Insertions

After inserting the words ["dog", "deer", "deal"] into an empty Trie, which of the following words will the search function return true for?

A ["deer", "deal"]

B ["dog", "deer", "deal"]

C ["dog", "deal"]

D ["dog", "deer"]

💡 Hint

Only words inserted fully will return true on search.

All three words are inserted fully, so searching any of them returns true.

❓ Predict Output

expert

Output of Trie Prefix Search Function

What is the output of the following C++ code that checks if any word in the Trie starts with a given prefix?

DSA C++

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

struct TrieNode {
    TrieNode* children[26];
    bool isEndOfWord;
    TrieNode() {
        for (int i = 0; i < 26; i++) children[i] = nullptr;
        isEndOfWord = false;
    }
};

class Trie {
public:
    TrieNode* root;
    Trie() { root = new TrieNode(); }

    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->isEndOfWord = true;
    }

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

int main() {
    Trie trie;
    trie.insert("hello");
    trie.insert("helium");
    cout << boolalpha;
    cout << trie.startsWith("hel") << endl;
    cout << trie.startsWith("hey") << endl;
    cout << trie.startsWith("hello") << endl;
    cout << trie.startsWith("helloo") << endl;
    return 0;
}

A

true
false
true
false

B

true
false
true
true

C

false
false
true
false

D

true
true
true
false

💡 Hint

startsWith returns true if prefix exists, even if not a full word.

"hel" is a prefix of both "hello" and "helium", so true.
"hey" is not a prefix of any word, so false.
"hello" is a prefix (and a full word), so true.
"helloo" is longer than any inserted word, so false.