Trie Insert Operation in DSA C++

Mental Model

A trie stores words by branching letters step-by-step, making it easy to find or add words by following paths of letters.

Analogy: Imagine a tree where each branch is a letter, and to write a word, you walk down branches matching each letter until the word ends.

root
 ↓
[a] -> [b] -> [c]
 ↑
current position

Dry Run Walkthrough

Input: Insert the word "cat" into an empty trie

Goal: Add the word "cat" so each letter is a node connected in order, marking the end of the word

Step 1: Start at root node, check if 'c' child exists

root -> []
 ↑

Why: We need to find or create the first letter node for 'c'

Step 2: Create 'c' node as child of root

root -> [c]
       ↑

Why: 'c' is the first letter, so we add it as a new branch

Step 3: Move to 'c' node, check if 'a' child exists

root -> [c] -> []
             ↑

Why: Next letter 'a' needs to be added after 'c'

Step 4: Create 'a' node as child of 'c'

root -> [c] -> [a]
                 ↑

Why: 'a' is next letter, so add it as a new branch

Step 5: Move to 'a' node, check if 't' child exists

root -> [c] -> [a] -> []
                       ↑

Why: Next letter 't' needs to be added after 'a'

Step 6: Create 't' node as child of 'a'

root -> [c] -> [a] -> [t]
                           ↑

Why: 't' is last letter, so add it as a new branch

Step 7: Mark 't' node as end of word

root -> [c] -> [a] -> [t*]
                           ↑

Why: Marking end shows the word "cat" is complete here

Result:

root -> [c] -> [a] -> [t*]

Word "cat" inserted with 't' marked as end

Annotated Code

DSA C++

#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isEndOfWord;

    TrieNode() {
        isEndOfWord = false;
    }
};

class Trie {
private:
    TrieNode* root;

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

    void insert(const string& word) {
        TrieNode* curr = root;
        for (char ch : word) {
            if (curr->children.find(ch) == curr->children.end()) {
                curr->children[ch] = new TrieNode();
            }
            curr = curr->children[ch];
        }
        curr->isEndOfWord = true;
    }

    void printTrie(TrieNode* node, string prefix) {
        if (node->isEndOfWord) {
            cout << prefix << "\n";
        }
        for (auto& pair : node->children) {
            printTrie(pair.second, prefix + pair.first);
        }
    }

    void print() {
        printTrie(root, "");
    }
};

int main() {
    Trie trie;
    trie.insert("cat");
    trie.print();
    return 0;
}

for (char ch : word) {

iterate over each letter in the word to insert

if (curr->children.find(ch) == curr->children.end()) {

check if current letter node exists; if not, create it

curr->children[ch] = new TrieNode();

create new node for the letter

curr = curr->children[ch];

move current pointer to the child node for next iteration

curr->isEndOfWord = true;

mark the last node as end of a word

Output

cat

Complexity Analysis

Time: O(m) because we process each of the m letters in the word once during insertion

Space: O(m) because in the worst case we add a new node for each letter in the word

vs Alternative: Compared to storing words in a list and searching linearly (O(n*m)), trie insertion is faster for prefix-based operations

Edge Cases

Inserting an empty string

No new nodes are added; root's isEndOfWord is set to true

DSA C++

for (char ch : word) {

Inserting a word that is a prefix of an existing word (e.g., insert "ca" after "cat")

Existing nodes are reused; only the end marker is updated

DSA C++

curr->isEndOfWord = true;

Inserting a word that shares prefix but diverges (e.g., insert "car" after "cat")

Common prefix nodes reused; new nodes created for differing letters

DSA C++

if (curr->children.find(ch) == curr->children.end()) {

When to Use This Pattern

When you need to store or search many words by their prefixes efficiently, use the Trie Insert Operation to build a prefix tree.

Common Mistakes

Mistake: Not marking the last node as end of word, causing search to fail for complete words
Fix: Set isEndOfWord = true on the last node after inserting all letters

Mistake: Creating new nodes for letters that already exist, duplicating branches
Fix: Check if child node exists before creating a new one

Summary

Inserts a word letter-by-letter into a trie, creating nodes as needed and marking the end.

Use when you want fast prefix-based word storage and lookup.

The key is to follow or create nodes for each letter and mark the last node as a word end.

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