Trie Insert Operation in DSA C++ - Execution Trace

Concept Flow - Trie Insert Operation

Start at root node

↓

For each character in word

↓

Check if child node exists

↓

Move to child

↓

Mark end of word at last node

↓

Done

Start at the root. For each letter, move to the child node if it exists; otherwise, create it. At the last letter, mark the node as end of word.

Execution Sample

DSA C++

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

Inserts a word into the trie by creating nodes for missing letters and marking the last node as end of word.

Execution Table

Step	Operation	Current Character	Node Created	Pointer Changes	Trie Visual State
1	Start insertion	-	No	current = root	root (empty)
2	Process 'c'	c	Yes	root->children['c' - 'a'] = new node; current moves to 'c'	root └─ c
3	Process 'a'	a	Yes	'c'->children['a' - 'a'] = new node; current moves to 'a'	root └─ c └─ a
4	Process 't'	t	Yes	'a'->children['t' - 'a'] = new node; current moves to 't'	root └─ c └─ a └─ t
5	Mark end of word	-	No	current->isEnd = true	root └─ c └─ a └─ t*
6	Insertion complete	-	No	-	root └─ c └─ a └─ t*

💡 All characters processed; last node marked as end of word.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
current	root	node 'c'	node 'a'	node 't'	node 't'	node 't'
Node Created	No	Yes (c)	Yes (a)	Yes (t)	No	No
isEnd flag	false	false	false	false	true	true

Key Moments - 3 Insights

Why do we create a new node only if the child does not exist?

Because if the child node already exists, it means that prefix is shared with another word, so we just move the pointer forward (see execution_table steps 2-4). Creating a new node only when missing avoids overwriting existing paths.

Why do we mark isEnd = true only after processing all characters?

Marking isEnd true at the last node indicates the end of a valid word in the trie (see execution_table step 5). If we marked it earlier, it would incorrectly mark prefixes as complete words.

What happens if we insert a word that is a prefix of an existing word?

We traverse existing nodes without creating new ones and mark the last node's isEnd true (not shown here but similar to steps 2-5). This allows the trie to store both the prefix and the longer word.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, which node does 'current' point to?

A Node 'a'

B Node 'c'

C Node 't'

D Root node

💡 Hint

Check the 'Pointer Changes' and 'Current Character' columns at step 3.

At which step is the isEnd flag set to true?

A Step 2

B Step 5

C Step 4

D Step 6

💡 Hint

Look at the 'Operation' and 'isEnd flag' changes in execution_table and variable_tracker.

If the word inserted was 'ca' instead of 'cat', how would the trie visual state change at the end?

A root → c*

B root → c → a → t*

C root → c → a* (isEnd true at 'a')

D root → a → t*

💡 Hint

Consider marking isEnd true at the last character node of the inserted word.

Concept Snapshot

Trie Insert Operation:
- Start at root node.
- For each character, check if child exists.
- If no child, create new node.
- Move current pointer to child node.
- After last char, mark node as end of word.
- Shared prefixes reuse nodes.

Full Transcript

The Trie Insert Operation starts at the root node. For each character in the word, it checks if a child node exists. If it does, the pointer moves to that child. If not, a new node is created and the pointer moves there. After processing all characters, the last node is marked as the end of a word. This process allows efficient storage of words sharing prefixes by reusing nodes. The execution table shows each step, node creation, pointer movement, and the trie structure growing. The variable tracker follows the current pointer and isEnd flag changes. Key moments clarify why nodes are created only when missing and why marking the end of word happens last. The visual quiz tests understanding of pointer positions, flag setting, and trie structure changes when inserting different 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