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 for char exists?

No→Create new child node

↓

Link new node to parent

↓

Move to child node

↓

After last char, mark node as end of word

↓

Done

Insert each character by traversing or creating nodes, then mark the last node as word end.

Execution Sample

DSA C#

Trie trie = new Trie();
trie.Insert("cat");
trie.Insert("car");
trie.Insert("bat");

Insert words "cat", "car", and "bat" into an empty trie step-by-step.

Execution Table

Step	Operation	Current Character	Node Created	Pointer Changes	Trie Visual State
1	Start Insert 'cat'	c	Yes (node 'c')	root.children['c'] → new node 'c'	root └─ c (not end)
2	Insert 'a'	a	Yes (node 'a')	node 'c'.children['a'] → new node 'a'	root └─ c └─ a (not end)
3	Insert 't'	t	Yes (node 't')	node 'a'.children['t'] → new node 't'	root └─ c └─ a └─ t (not end)
4	Mark 't' as end of word	t	No	node 't'.isEnd = true	root └─ c └─ a └─ t (end)
5	Start Insert 'car'	c	No	move to node 'c'	root └─ c └─ a └─ t (end)
6	Insert 'a'	a	No	move to node 'a'	root └─ c └─ a └─ t (end)
7	Insert 'r'	r	Yes (node 'r')	node 'a'.children['r'] → new node 'r'	root └─ c └─ a ├─ t (end) └─ r (not end)
8	Mark 'r' as end of word	r	No	node 'r'.isEnd = true	root └─ c └─ a ├─ t (end) └─ r (end)
9	Start Insert 'bat'	b	Yes (node 'b')	root.children['b'] → new node 'b'	root ├─ c │ └─ a │ ├─ t (end) │ └─ r (end) └─ b (not end)
10	Insert 'a'	a	Yes (node 'a')	node 'b'.children['a'] → new node 'a'	root ├─ c │ └─ a │ ├─ t (end) │ └─ r (end) └─ b └─ a (not end)
11	Insert 't'	t	Yes (node 't')	node 'a'.children['t'] → new node 't'	root ├─ c │ └─ a │ ├─ t (end) │ └─ r (end) └─ b └─ a └─ t (not end)
12	Mark 't' as end of word	t	No	node 't'.isEnd = true	root ├─ c │ └─ a │ ├─ t (end) │ └─ r (end) └─ b └─ a └─ t (end)
13	End of insertions	-	-	-	Insertion complete for all words

💡 All characters inserted and last nodes marked as end of words.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 7	After Step 12	Final
Current Node	root	node 'c'	node 't'	node 'r'	node 't' (end) under 'b->a'	final node 't' of 'bat'
Trie Size (nodes)	1 (root)	2 (root + c)	4 (root + c + a + t)	5 (added r under a)	8 (added b, a, t)	8 nodes total

Key Moments - 3 Insights

Why do we create new nodes only when the child for a character doesn't exist?

Because existing nodes represent shared prefixes. Creating new nodes only when needed avoids duplication and keeps the trie compact, as shown in steps 5-7 where 'car' shares 'c' and 'a' nodes with 'cat'.

Why do we mark the last node as end of word instead of storing the whole word?

Marking the last node as end of word indicates a complete word ends there, allowing shared prefixes. This is shown in steps 4, 8, and 12 where nodes 't' and 'r' are marked to distinguish 'cat', 'car', and 'bat'.

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

We just mark the node corresponding to the last character as end of word without creating new nodes. This is not shown here but follows the same logic as marking nodes in steps 4, 8, and 12.

Visual Quiz - 3 Questions

Look at the execution table, at which step is the node for character 'r' created?

A Step 7

B Step 6

C Step 8

D Step 5

💡 Hint

Check the 'Node Created' column in the execution table for character 'r'.

According to the variable tracker, how many nodes are in the trie after inserting 'cat'?

A 3

B 4

C 2

D 1

💡 Hint

Look at 'Trie Size (nodes)' after Step 3 in the variable tracker.

If we insert the word 'ca' after these insertions, what change happens in the trie?

A New nodes for 'c' and 'a' are created

B Only the node for 'a' is marked as end of word

C No changes happen

D A new branch is created under 'c'

💡 Hint

Refer to key moment 3 about inserting a prefix word.

Concept Snapshot

Trie Insert Operation:
- Start at root node
- For each char: if child exists, move; else create new node
- After last char, mark node as end of word
- Shares prefixes to save space
- Efficient for prefix searches

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 not, it creates a new node and links it. It moves to the child node and repeats until all characters are processed. Finally, it marks the last node as the end of a word. This process allows sharing prefixes among words, saving space. The execution table shows step-by-step node creation and pointer updates for inserting 'cat', 'car', and 'bat'. The variable tracker monitors the current node and total nodes in the trie. Key moments clarify why nodes are created only when needed, why marking end of word is important, and what happens when inserting a prefix word. The visual quiz tests understanding of node creation steps, trie size, and prefix insertion effects.

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 search for a word in the Trie

D. To add a word character by character into the Trie

Solution

1. Step 1: Understand the Insert operation

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

2. Step 2: Compare with other operations

   Deleting removes words, searching finds words, counting totals words. Insert specifically adds words.

3. Final Answer:

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

4. Quick Check:

   Insert = Add word step-by-step [OK]

Hint: Insert means adding word letters one by one [OK]

Common Mistakes:

• Confusing Insert with Delete or Search
• Thinking Insert counts words
• Assuming Insert removes nodes

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

easy

A. public class TrieNode { public Dictionary Children = new Dictionary(); public bool IsEndOfWord = false; }

B. public class TrieNode { public List<int> Children; public bool IsEndOfWord; }

C. public class TrieNode { public int[] Children = new int[26]; public bool IsEndOfWord; }

D. public class TrieNode { public string Children; public bool IsEndOfWord; }

Solution

1. Step 1: Identify correct data structure for children

   Trie nodes use a dictionary mapping characters to child nodes for flexible branching.

2. Step 2: Check class members

   public class TrieNode { public Dictionary Children = new Dictionary(); public bool IsEndOfWord = false; } uses Dictionary and a boolean flag for word end, which is standard.

3. Final Answer:

   public class TrieNode { public Dictionary Children = new Dictionary(); public bool IsEndOfWord = false; } -> Option A

4. Quick Check:

   Children dictionary + end flag = public class TrieNode { public Dictionary Children = new Dictionary(); public bool IsEndOfWord = false; } [OK]

Hint: Use Dictionary for children in C# Trie nodes [OK]

Common Mistakes:

• Using List<int> instead of dictionary for children
• Using int array without node references
• Using string instead of node references

3. Consider the following C# code inserting the word "cat" into an empty Trie. What will be the state of the root node's children after insertion?

Trie trie = new Trie();
trie.Insert("cat");
var childrenKeys = trie.Root.Children.Keys.ToList();
childrenKeys.Sort();
Console.WriteLine(string.Join(",", childrenKeys));

medium

A. "t"

B. "a"

C. "c"

D. "cat"

Solution

1. Step 1: Insert "cat" character by character

   First character 'c' is added as a child of root node.

2. Step 2: Check root's children keys

   Only 'c' is directly under root; 'a' and 't' are children of subsequent nodes.

3. Final Answer:

   "c" -> Option C

4. Quick Check:

   Root children keys = first letter only [OK]

Hint: Root children keys = first letters of inserted words [OK]

Common Mistakes:

• Assuming all letters appear at root children
• Confusing nested children with root children
• Printing full word as a key

4. The following C# code attempts to insert the word "dog" into a Trie but has a bug. What is the error?

public void Insert(string word) {
    var node = Root;
    foreach (char c in word) {
        if (!node.Children.ContainsKey(c)) {
            node.Children[c] = new TrieNode();
        }
        node = node.Children[c];
    }
    node.IsEndOfWord = false;
}

medium

A. The IsEndOfWord flag should be set to true after insertion

B. The foreach loop should iterate backwards

C. Children dictionary should be cleared before insertion

D. Root node should be reinitialized inside the method

Solution

1. Step 1: Analyze IsEndOfWord assignment

   After inserting all characters, IsEndOfWord marks the end of a valid word and must be true.

2. Step 2: Identify the bug

   Code sets IsEndOfWord to false, which incorrectly marks the word as not complete.

3. Final Answer:

   The IsEndOfWord flag should be set to true after insertion -> Option A

4. Quick Check:

   End flag = true after insert [OK]

Hint: Set IsEndOfWord = true after inserting full word [OK]

Common Mistakes:

• Setting IsEndOfWord to false instead of true
• Reinitializing root unnecessarily
• Clearing children during insert

5. You want to insert multiple words into a Trie and then check if the word "bat" exists. Which sequence of operations correctly inserts "bat", "ball", and "batman" and marks them properly in C#?

hard

A. Insert "bat", Insert "ball", Insert "batman"; set IsEndOfWord true at root node

B. Insert "bat", Insert "ball", Insert "batman"; set IsEndOfWord true only at last character of each word

C. Insert "bat", Insert "ball", Insert "batman"; set IsEndOfWord true for all nodes

D. Insert "bat", Insert "ball", Insert "batman"; set IsEndOfWord false for all nodes

Solution

1. Step 1: Insert each word fully

   Insert each word character by character, creating nodes as needed.

2. Step 2: Mark end of each word

   Set IsEndOfWord = true only at the last character node of each inserted word to mark valid words.

3. Final Answer:

   Insert "bat", Insert "ball", Insert "batman"; set IsEndOfWord true only at last character of each word -> Option B

4. Quick Check:

   End flag true only at word ends [OK]

Hint: Mark end flag true only at last letter of each word [OK]

Common Mistakes:

• Marking root or all nodes as end of word
• Not marking end of word nodes
• Setting end flag false after insert