Trie Search Operation in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Trie data structure?

A Trie is a tree-like data structure used to store a dynamic set of strings where keys are usually strings. Each node represents a character, and paths from the root to leaves represent words.

beginner

What does the search operation in a Trie do?

The search operation checks if a given word exists in the Trie by following nodes corresponding to each character of the word. If all characters are found and the last node marks the end of a word, the search returns true.

beginner

In Trie search, what happens if a character node is missing during traversal?

If a character node is missing while traversing the Trie for a word, it means the word does not exist in the Trie, so the search returns false immediately.

intermediate

Why does Trie search have a time complexity of O(m), where m is the length of the word?

Because the search operation checks each character of the word once by moving down the Trie nodes, the time depends only on the word length, not the number of words stored.

beginner

What is the role of the 'isEndOfWord' flag in Trie nodes during search?

The 'isEndOfWord' flag indicates if the current node marks the end of a valid word. During search, even if all characters match, the word is considered found only if this flag is true at the last character node.

What does the Trie search operation return if a character node is missing?

A True

B Returns null

C It continues searching

D False

If a character node is missing during traversal, the word does not exist in the Trie, so search returns false.

What does the 'isEndOfWord' flag signify in a Trie node?

A Start of a word

B Middle of a word

C End of a valid word

D Node is empty

The 'isEndOfWord' flag marks that the node represents the end of a valid word stored in the Trie.

What is the time complexity of searching a word of length m in a Trie?

A O(1)

B O(m)

C O(n)

D O(m*n)

Trie search time depends on the length of the word m, so it is O(m).

If a Trie contains the words 'cat' and 'car', what will searching for 'ca' return?

A False

B Depends on implementation

C True

D Error

Even though 'ca' is a prefix, it is not a complete word in the Trie unless 'isEndOfWord' is true at 'a' node, so search returns false.

During Trie search, what is the first step for each character in the word?

A Check if the character node exists among children

B Add the character node

C Delete the character node

D Mark the node as end of word

For each character, search checks if the corresponding child node exists to continue traversal.

Explain how the search operation works in a Trie data structure.

Think about following the path of characters and checking the end marker.

Why is Trie search efficient compared to searching in a list of words?

Consider how Trie organizes words by common prefixes.

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