Trie Search Operation in DSA C++ - Build from Scratch

Trie Search Operation

📖 Scenario: Imagine you are building a simple phone contact search system. You want to quickly check if a contact name exists in your phone book.

🎯 Goal: Build a Trie data structure and implement a search operation to check if a given contact name exists.

📋 What You'll Learn

Create a TrieNode class with an array of 26 children pointers and a boolean to mark end of word

Create a Trie class with insert and search methods

Insert given contact names into the Trie

Search for a specific contact name using the Trie search method

Print true if the contact exists, otherwise false

💡 Why This Matters

🌍 Real World

Tries are used in phone contact search, autocomplete, and spell checking to quickly find words or prefixes.

💼 Career

Understanding Trie search operations is important for roles involving text processing, search engines, and efficient data retrieval.

1

Create TrieNode class and Trie class with insert method

Create a class called TrieNode with a public boolean isEndOfWord set to false and an array of 26 TrieNode* called children initialized to nullptr. Then create a class called Trie with a public TrieNode* called root initialized to a new TrieNode. Add a public method insert that takes a string word and inserts it into the Trie.

DSA C++

// Your code here

Hint

Define the TrieNode with 26 children pointers and a boolean flag. In Trie, initialize root and implement insert by traversing characters and creating nodes.

2

Add search method to Trie class

Add a public method search to the Trie class that takes a string word and returns true if the word exists in the Trie, otherwise false. Use a for loop with variable c to traverse the Trie nodes.

DSA C++

#include 
#include 
using namespace std;

class TrieNode {
public:
    bool isEndOfWord;
    TrieNode* children[26];
    TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i children[index] == nullptr) {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
        }
        node->isEndOfWord = true;
    }

    // Add search method here
    // Your code here
};

Hint

Traverse the Trie for each character. If a child node is missing, return false. After the loop, return if current node marks end of word.

3

Insert contact names into the Trie

Create a Trie object called trie. Insert the following contact names into the Trie using the insert method: "alice", "bob", "carol", "dave".

DSA C++

#include 
#include 
using namespace std;

class TrieNode {
public:
    bool isEndOfWord;
    TrieNode* children[26];
    TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i children[index] == nullptr) {
                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] == nullptr) {
                return false;
            }
            node = node->children[index];
        }
        return node->isEndOfWord;
    }
};

int main() {
    Trie trie;
    // Insert contacts here
    // Your code here
    return 0;
}

Hint

Create a Trie object and call insert for each contact name exactly as given.

4

Search for a contact and print the result

Use the search method of the trie object to check if the contact name "carol" exists. Print true if it exists, otherwise print false.

DSA C++

#include 
#include 
using namespace std;

class TrieNode {
public:
    bool isEndOfWord;
    TrieNode* children[26];
    TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i children[index] == nullptr) {
                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] == nullptr) {
                return false;
            }
            node = node->children[index];
        }
        return node->isEndOfWord;
    }
};

int main() {
    Trie trie;
    trie.insert("alice");
    trie.insert("bob");
    trie.insert("carol");
    trie.insert("dave");
    // Print search result for "carol"
    // Your code here
    return 0;
}

Hint

Call trie.search("carol") and print true if found, else false.

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