Trie Search Operation in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the current character exists in the children map.

DSA C++

if (node->children.find(word[[1]]) == node->children.end()) {
    return false;
}

Drag options to blanks, or click blank then click option'

Aword

B0

Cnode

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using the whole word instead of an index.

Using a variable not defined in the loop.

We use 'i' as the index to access each character in the word during traversal.

2fill in blank

medium

Complete the code to move to the next node in the trie for the current character.

DSA C++

node = node->children[[1]];

Drag options to blanks, or click blank then click option'

Ai

Bnode

Cword[i]

Dchildren

Attempts:

3 left

💡 Hint

Common Mistakes

Using the index 'i' directly instead of the character.

Using 'node' or 'children' which are not keys.

We use word[i] to get the current character and move to its child node.

3fill in blank

hard

Fix the error in the return statement to check if the word ends at this node.

DSA C++

return node->[1];

Drag options to blanks, or click blank then click option'

AisEnd

BisWord

CendOfWord

DwordEnd

Attempts:

3 left

💡 Hint

Common Mistakes

Using incorrect flag names like 'isWord' or 'endOfWord'.

Forgetting to check this flag.

The boolean flag 'isEnd' indicates if the node marks the end of a word.

4fill in blank

hard

Fill both blanks to complete the for loop that iterates over each character in the word.

DSA C++

for (int [1] = 0; [2] < word.size(); ++[1]) {
    // loop body
}

Drag options to blanks, or click blank then click option'

Ai

Bj

Ck

Dindex

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names in the loop condition and increment.

Using a variable not declared.

The loop variable 'i' is used consistently to iterate over the word characters.

5fill in blank

hard

Fill all three blanks to complete the search function that returns true if the word exists in the trie.

DSA C++

bool search(string word) {
    TrieNode* node = root;
    for (int [1] = 0; [2] < word.size(); ++[1]) {
        if (node->children.find(word[[3]]) == node->children.end()) {
            return false;
        }
        node = node->children[word[[3]]];
    }
    return node->isEnd;
}

Drag options to blanks, or click blank then click option'

Ai

Bj

Ck

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variables for loop and indexing.

Using a constant index instead of the loop variable.

The loop variable 'i' is used consistently to index characters in the word during traversal.

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