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

Trie Insert Operation

📖 Scenario: Imagine you are building a simple search feature that suggests words as you type. To do this efficiently, you use a data structure called a Trie. A Trie stores words so you can quickly find them by their prefixes.

🎯 Goal: You will build the insert operation for a Trie in C++. This means you will add words to the Trie one letter at a time, creating new nodes if needed.

📋 What You'll Learn

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

Create a Trie class with a root node

Write an insert function that adds a word to the Trie letter by letter

Print the Trie structure after inserting words to verify the insert operation

💡 Why This Matters

🌍 Real World

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

💼 Career

Understanding Trie insertions helps in roles involving search engines, text processing, and efficient data retrieval.

1

Create TrieNode class

Create a class called TrieNode with a public boolean variable isEndOfWord initialized to false and a public array of 26 TrieNode* pointers called children initialized to nullptr.

DSA C++

# Your code here

Hint

Think of children as 26 branches for each letter a-z. Initialize all to nullptr and isEndOfWord to false.

2

Create Trie class with root node

Create a class called Trie with a public pointer variable root of type TrieNode*. Initialize root in the constructor by creating a new TrieNode.

DSA C++

class TrieNode {
public:
    bool isEndOfWord;
    TrieNode* children[26];

    TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
    }
};

// Your code here

Hint

The Trie class needs a root node to start all insertions. Create it in the constructor.

3

Implement insert function

Inside the Trie class, write a public function called insert that takes a const std::string& word. Use a pointer node starting at root. For each character in word, calculate its index as ch - 'a'. If node->children[index] is nullptr, create a new TrieNode. Move node to node->children[index]. After the loop, set node->isEndOfWord to true.

DSA C++

class TrieNode {
public:
    bool isEndOfWord;
    TrieNode* children[26];

    TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
    }
};

class Trie {
public:
    TrieNode* root;

    Trie() {
        root = new TrieNode();
    }

    // Implement insert function here
    // Your code here
};

Hint

Think of walking down the branches for each letter. If a branch is missing, create it. Mark the last node as the end of a word.

4

Print Trie structure after insertions

In the main function, create a Trie object called trie. Insert the words "cat", "car", and "dog" using trie.insert. Then print "Inserted words: cat, car, dog" to confirm insertion.

DSA C++

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

int main() {
    // Your code here
}

Hint

Use std::cout to print the confirmation message after inserting all words.