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.

Practice

1. What is the main purpose of the insert operation in a Trie data structure?

easy

A. To count the number of words stored in the Trie

B. To delete a word from the Trie

C. To add a new word character by character into the Trie

D. To search for a word in the Trie

Solution

1. Step 1: Understand the insert operation

   The insert operation adds each character of a word into the Trie, creating nodes if they don't exist.

2. Step 2: Differentiate from other operations

   Deleting removes words, searching checks presence, counting totals words. Insert specifically adds words.

3. Final Answer:

   To add a new word character by character into the Trie -> Option C

4. Quick Check:

   Insert = Add word [OK]

Hint: Insert means adding word step-by-step [OK]

Common Mistakes:

• Confusing insert with search or delete
• Thinking insert counts words
• Assuming insert replaces existing words

2. Which of the following is the correct way to declare a Trie node class in C++ for insertion?

easy

A. class TrieNode { public: vector<char> children; bool isEnd; TrieNode() { isEnd = false; } };

B. class TrieNode { public: int children[26]; bool isEnd; TrieNode() { for(int i=0; i<26; i++) children[i] = 0; isEnd = false; } };

C. class TrieNode { public: TrieNode children[26]; bool isEnd; TrieNode() { isEnd = false; } };

D. class TrieNode { public: TrieNode* children[26]; bool isEnd; TrieNode() { for(int i=0; i<26; i++) children[i] = nullptr; isEnd = false; } };

Solution

1. Step 1: Check children type for TrieNode

   Children must be pointers to TrieNode to allow dynamic node creation; hence TrieNode* children[26].

2. Step 2: Verify initialization

   Initialize all children pointers to nullptr and isEnd to false in constructor.

3. Final Answer:

   class TrieNode { public: TrieNode* children[26]; bool isEnd; TrieNode() { for(int i=0; i<26; i++) children[i] = nullptr; isEnd = false; } }; -> Option D

4. Quick Check:

   Children pointers + init nullptr = class TrieNode { public: TrieNode* children[26]; bool isEnd; TrieNode() { for(int i=0; i<26; i++) children[i] = nullptr; isEnd = false; } }; [OK]

Hint: Children must be pointers, initialized to nullptr [OK]

Common Mistakes:

• Using int array instead of pointers
• Not initializing children to nullptr
• Using vector<char> instead of TrieNode pointers

3. What will be the output of the following code snippet after inserting the words "cat" and "car" into an empty Trie?

Trie trie;
trie.insert("cat");
trie.insert("car");
int count = 0;
for(int i = 0; i < 26; i++) {
  if(trie.root->children[i] != nullptr) count++;
}
std::cout << count << std::endl;

medium

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Insert "cat" and "car" into Trie

   Both words start with 'c', so only one child node for 'c' is created at root.

2. Step 2: Count root children nodes

   Only one child at root for 'c' exists, so count is 1.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   Root children count after insert = 1 [OK]

Hint: Count root children after insert; common prefix shares node [OK]

Common Mistakes:

• Counting all characters instead of root children
• Assuming separate root nodes for each word
• Confusing total nodes with root children

4. Identify the error in the following Trie insert function snippet:

void insert(string word) {
  TrieNode* node = root;
  for(char c : word) {
    int index = c - 'a';
    if(node->children[index] == NULL) {
      node->children[index] = new TrieNode();
    }
    node = node->children[index];
  }
  node->isEnd = true;
}

medium

A. No error; the insert function is correct

B. The index calculation should be c - 'A' instead of c - 'a'

C. The root pointer is not initialized before insertion

D. The loop should iterate over indices, not characters

Solution

1. Step 1: Check root initialization assumption

   Assuming root is properly initialized elsewhere, this code correctly uses root pointer.

2. Step 2: Verify index calculation and loop

   Index c - 'a' is correct for lowercase letters; loop over characters is valid.

3. Final Answer:

   No error; the insert function is correct -> Option A

4. Quick Check:

   Code logic matches standard insert [OK]

Hint: Check index and pointer usage carefully [OK]

Common Mistakes:

• Assuming uppercase letters without context
• Thinking loop must use indices
• Forgetting root initialization outside snippet

5. Given a Trie that already contains the words "bat", "ball", and "barn", what will be the effect of inserting the word "bar"?
Choose the correct statement.

hard

A. A new branch is created starting from 'b' node

B. No new nodes are created; only an existing node's isEnd flag is set

C. All existing nodes are duplicated to insert the new word

D. The word "bar" cannot be inserted because "barn" exists

Solution

1. Step 1: Analyze existing Trie structure

   Words "bat", "ball", "barn" share prefix 'ba' and 'bar' prefix exists as part of "barn".

2. Step 2: Effect of inserting "bar"

   Nodes for 'b', 'a', 'r' already exist; only isEnd flag at 'r' node is set to true to mark "bar" as a word.

3. Final Answer:

   No new nodes are created; only an existing node's isEnd flag is set -> Option B

4. Quick Check:

   Insert existing prefix sets isEnd only [OK]

Hint: Insert existing prefix sets isEnd flag only [OK]

Common Mistakes:

• Thinking new nodes are always created
• Assuming duplicates of nodes happen
• Believing insertion fails if prefix exists