Trie Insert Operation in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a new TrieNode when the character is not present.

DSA C#

if (!node.Children.ContainsKey(ch)) {
    node.Children[[1]] = new TrieNode();
}

Drag options to blanks, or click blank then click option'

Ach

Bnode

Croot

Dword

Attempts:

3 left

💡 Hint

Common Mistakes

Using the node variable instead of the character as the key.

Using the root or word variable which are not keys in the children dictionary.

The character ch is used as the key to add a new child node in the Trie.

2fill in blank

medium

Complete the code to move to the next node after inserting or finding the character.

DSA C#

node = node.[1][ch];

Drag options to blanks, or click blank then click option'

AChildren

BNodes

CNext

DLinks

Attempts:

3 left

💡 Hint

Common Mistakes

Using incorrect property names like Nodes or Next which do not exist.

Trying to access a list or array instead of a dictionary.

The Children dictionary holds the next nodes for each character.

3fill in blank

hard

Fix the error in marking the end of a word after insertion.

DSA C#

node.[1] = true;

Drag options to blanks, or click blank then click option'

AEndOfWord

BIsEnd

CIsWord

DIsComplete

Attempts:

3 left

💡 Hint

Common Mistakes

Using properties that do not exist like IsEnd or EndOfWord.

Forgetting to mark the end of the word which causes search errors.

The property IsWord is used to mark the node as the end of a valid word.

4fill in blank

hard

Fill both blanks to complete the insert method for the Trie.

DSA C#

public void Insert(string word) {
    var node = root;
    foreach (var ch in word) {
        if (!node.Children.ContainsKey([1])) {
            node.Children[[2]] = new TrieNode();
        }
        node = node.Children[ch];
    }
    node.IsWord = true;
}

Drag options to blanks, or click blank then click option'

Ach

Bword

Cnode

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variables for the two blanks causing errors.

Using the word or node variable instead of the character.

Both blanks require the current character ch to check and add the child node.

5fill in blank

hard

Fill all three blanks to complete the insert method with correct variable usage.

DSA C#

public void Insert(string word) {
    var [1] = root;
    foreach (var [2] in word) {
        if (!node.Children.ContainsKey(ch)) {
            node.Children[ch] = new TrieNode();
        }
        [3] = node.Children[ch];
    }
    node.IsWord = true;
}

Drag options to blanks, or click blank then click option'

Anode

Bch

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Using inconsistent variable names causing confusion.

Not updating the node variable correctly inside the loop.

node is the current node, ch is the current character, and node is updated to the child node.

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