Why Trie Search Operation in DSA C++?

The Big Idea

What if you could find any word instantly without flipping through pages?

The Scenario

Imagine you have a huge phone book with thousands of names. You want to find if a name exists, but you have to flip through every page manually.

The Problem

Searching manually is slow and tiring. You might miss names or take a long time to find one. It's easy to get lost or confused with so many entries.

The Solution

A Trie organizes words like a tree, where each letter leads you closer to the full word. This way, you quickly jump to the right place without checking every name.

Before vs After

✗ Before

bool searchName(vector<string> &names, string target) {
  for (int i = 0; i < names.size(); i++) {
    if (names[i] == target) return true;
  }
  return false;
}

✓ After

bool searchInTrie(TrieNode* root, string word) {
  TrieNode* current = root;
  for (char ch : word) {
    if (!current->children[ch - 'a']) return false;
    current = current->children[ch - 'a'];
  }
  return current->isEndOfWord;
}

What It Enables

It lets you find words instantly, even in huge collections, by following letter paths instead of checking each word one by one.

Real Life Example

When you type a search in your phone's contact list, the phone uses a Trie to quickly find matching names as you type each letter.

Key Takeaways

Manual search checks every word, which is slow.

Trie search follows letters step-by-step, making it fast.

Tries help in autocomplete, spell check, and fast word lookup.

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