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.

Practice

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

easy

A. To store words in a linked list

B. To sort words alphabetically

C. To efficiently store and search words by their prefixes

D. To perform arithmetic operations on words

Solution

1. Step 1: Understand Trie structure

   A Trie stores characters of words in a tree where each node represents a character, allowing prefix sharing.

2. Step 2: Identify Trie use in word search

   Because words share prefixes, Trie allows fast prefix-based search, making word search efficient.

3. Final Answer:

   To efficiently store and search words by their prefixes -> Option C

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie is best for prefix-based word search [OK]

Common Mistakes:

• Confusing Trie with sorting structures
• Thinking Trie stores words linearly
• Assuming Trie is for arithmetic

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

easy

A. class TrieNode { public: TrieNode* children[26]; bool isEndOfWord; };

B. class TrieNode { int data; TrieNode* next; };

C. struct TrieNode { vector<int> children; bool end; };

D. class TrieNode { char letter; TrieNode* left; TrieNode* right; };

Solution

1. Step 1: Check Trie node structure for word search

   Trie nodes typically have an array of pointers for 26 letters and a boolean to mark word end.

2. Step 2: Match with options

   class TrieNode { public: TrieNode* children[26]; bool isEndOfWord; }; matches this structure exactly with children array and isEndOfWord flag.

3. Final Answer:

   class TrieNode { public: TrieNode* children[26]; bool isEndOfWord; }; -> Option A

4. Quick Check:

   Trie node = children array + end flag [OK]

Hint: Trie nodes have 26 children pointers and end flag [OK]

Common Mistakes:

• Using linked list pointers instead of array
• Using vector<int> instead of pointers
• Confusing binary tree node with Trie node

3. What will be the output of the following C++ code snippet that inserts words into a Trie and searches for "cat"?

class TrieNode {
public:
    TrieNode* children[26] = {nullptr};
    bool 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("cat");
    trie.insert("car");
    trie.insert("dog");
    cout << (trie.search("cat") ? "Found" : "Not Found") << endl;
    return 0;
}

medium

A. Runtime Error

B. Found

C. Compilation Error

D. Not Found

Solution

1. Step 1: Insert words "cat", "car", "dog" into Trie

   Each word is inserted character by character, creating nodes and marking end of word for last character.

2. Step 2: Search for "cat" in Trie

   Traversal finds nodes for 'c', 'a', 't' and confirms isEndOfWord is true, so returns true.

3. Final Answer:

   Found -> Option B

4. Quick Check:

   Inserted word found = Found [OK]

Hint: Search returns true if end flag is set after traversal [OK]

Common Mistakes:

• Not marking isEndOfWord true on insert
• Returning true without checking end flag
• Off-by-one errors in indexing

4. Identify the bug in the following Trie search function and select the correct fix:

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;
}

medium

A. Add a check for null root pointer before loop

B. Remove the return statement inside the loop

C. Change 'node = node->children[index];' to 'node = node->children[index + 1];'

D. Change 'if (node->children[index])' to 'if (!node->children[index])'

Solution

1. Step 1: Analyze the if condition inside loop

   The condition 'if (node->children[index]) return false;' wrongly returns false if child exists, which is opposite logic.

2. Step 2: Correct the condition to check if child does NOT exist

   It should be 'if (!node->children[index]) return false;' to return false when path breaks.

3. Final Answer:

   Change 'if (node->children[index])' to 'if (!node->children[index])' -> Option D

4. Quick Check:

   Check for missing child = return false [OK]

Hint: Return false if child node is missing, not if present [OK]

Common Mistakes:

• Returning false when child exists
• Ignoring null pointer checks
• Incorrect index calculation

5. Given a list of words: ["apple", "app", "application", "bat", "bath", "batman"], how can a Trie be used to efficiently find all words starting with the prefix "app"? Choose the best approach.

hard

A. Insert all words into Trie, then traverse nodes for 'a'->'p'->'p' and collect all descendant words

B. Sort the list and perform binary search for prefix "app"

C. Use a hash map to store all words and check prefix by substring

D. Store words in a linked list and scan each word for prefix match

Solution

1. Step 1: Insert all words into Trie

   Each word is inserted character by character, building a prefix tree.

2. Step 2: Traverse Trie nodes for prefix "app"

   Follow nodes for 'a', 'p', 'p' to reach prefix node, then collect all words below it.

3. Step 3: Collect descendant words

   Perform DFS or BFS from prefix node to gather all words starting with "app" efficiently.

4. Final Answer:

   Insert all words into Trie, then traverse nodes for 'a'->'p'->'p' and collect all descendant words -> Option A

5. Quick Check:

   Trie prefix traversal + collect descendants = Insert all words into Trie, then traverse nodes for 'a'->'p'->'p' and collect all descendant words [OK]

Hint: Traverse prefix nodes then gather descendants in Trie [OK]

Common Mistakes:

• Using sorting instead of Trie for prefix search
• Checking prefix by substring on all words
• Scanning linked list inefficiently