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.