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

Word Search in Trie

📖 Scenario: Imagine you have a small dictionary of words and you want to quickly check if a word exists in it. A Trie is a tree-like data structure that helps you do this efficiently.In this project, you will build a simple Trie with a few words and then search for a specific word in it.

🎯 Goal: You will create a Trie with given words, set up a search word, write the search logic to check if the word exists in the Trie, and finally print the result.

📋 What You'll Learn

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

Insert given words into the Trie

Create a string variable for the word to search

Write a function to search the word in the Trie

Print 'Found' if the word exists, otherwise print 'Not Found'

💡 Why This Matters

🌍 Real World

Tries are used in autocomplete systems, spell checkers, and IP routing to quickly find words or prefixes.

💼 Career

Understanding Tries helps in software engineering roles involving text processing, search engines, and efficient data retrieval.

1

Create TrieNode class and insert words

Create a class called TrieNode with a public boolean isEndOfWord initialized to false and an array of 26 TrieNode* pointers called children initialized to nullptr. Then create a class called Trie with a public TrieNode* called root initialized to a new TrieNode. Finally, write a public method insert in Trie that takes a const string& called word and inserts it into the Trie by creating nodes for each character.

DSA C++

#include 
#include 
using namespace std;

// Create TrieNode class and Trie class with insert method
// Your code here

Hint

Remember to initialize all children pointers to nullptr in the TrieNode constructor.

In the insert method, create new nodes only if the child pointer is nullptr.

2

Set the word to search

Create a string variable called searchWord and set it to "cat".

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;
    }
};

// Create string variable searchWord and set it to "cat"
// Your code here

Hint

Just create a string variable named searchWord and assign it the value "cat".

3

Write search function in Trie

Add a public method bool search(const string& word) in the Trie class that returns true if the word exists in the Trie and false otherwise. Use a loop to traverse the Trie nodes for each character. Return node->isEndOfWord at the end.

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
};

string searchWord = "cat";

Hint

Traverse the Trie nodes for each character in the word.

If any character node is missing, return false.

At the end, return node->isEndOfWord to confirm the word exists.

4

Insert words, search and print result

Create a Trie object called trie. Insert the words "cat", "car", and "dog" into trie using the insert method. Then use the search method to check if searchWord exists in the Trie. Print "Found" if it exists, otherwise print "Not Found".

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(const string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            int index = ch - 'a';
            if (node->children[index] == nullptr) {
                return false;
            }
            node = node->children[index];
        }
        return node->isEndOfWord;
    }
};

string searchWord = "cat";

// Create Trie object trie
// Insert "cat", "car", "dog" into trie
// Search for searchWord and print "Found" or "Not Found"
// Your code here

Hint

Create a Trie object named trie.

Insert the words "cat", "car", and "dog" using trie.insert().

Use trie.search(searchWord) to check if the word exists.

Print "Found" if true, otherwise "Not Found".