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.