Trie Insert Operation in DSA C# - Build from Scratch

Trie Insert Operation

📖 Scenario: Imagine you are building a simple search feature for a phone contact list. You want to store names so that you can quickly find them later. A Trie is a special tree that helps store words letter by letter.

🎯 Goal: You will create a Trie data structure and write code to insert names into it. After inserting, you will print the Trie structure to see how names are stored.

📋 What You'll Learn

Create a TrieNode class with a dictionary for children and a boolean to mark end of word

Create a Trie class with an Insert method to add words letter by letter

Insert given names into the Trie using the Insert method

Print the Trie nodes to show the stored names

💡 Why This Matters

🌍 Real World

Tries are used in search engines, autocomplete features, and spell checkers to quickly find words sharing prefixes.

💼 Career

Understanding Trie insertions helps in roles involving text processing, search optimization, and building efficient data retrieval systems.

1

Create TrieNode class

Create a class called TrieNode with a public dictionary called Children of type Dictionary and a public boolean called IsEndOfWord initialized to false.

DSA C#

# Your code here

Hint

Think of TrieNode as a box holding letters and a flag to say if a word ends here.

2

Create Trie class with Insert method

Create a class called Trie with a public TrieNode variable called Root initialized in the constructor. Add a public method Insert that takes a string word and inserts it letter by letter into the Trie using Root.

DSA C#

using System.Collections.Generic;

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

// Create Trie class with Root and Insert method
# Your code here

Hint

Insert each letter by checking if it exists in Children. If not, add a new node. Mark the last node as end of word.

3

Insert names into the Trie

Create a Trie object called trie. Insert the names "Anna", "Anne", and "Ann" into trie using the Insert method.

DSA C#

using System.Collections.Generic;

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

public class Trie
{
    public TrieNode Root;

    public Trie()
    {
        Root = new TrieNode();
    }

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

// Create Trie object and insert names
# Your code here

Hint

Use the Insert method on the trie object for each name.

4

Print the Trie structure

Add a method PrintTrie in the Trie class that prints all words stored in the Trie. Call PrintTrie from Main to display the inserted names.

DSA C#

using System;
using System.Collections.Generic;

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

public class Trie
{
    public TrieNode Root;

    public Trie()
    {
        Root = new TrieNode();
    }

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

    // Add PrintTrie method here
    # Your code here
}

public class Program
{
    public static void Main()
    {
        Trie trie = new Trie();
        trie.Insert("Anna");
        trie.Insert("Anne");
        trie.Insert("Ann");

        // Call PrintTrie here
        # Your code here
    }
}

Hint

Use a recursive helper to build words and print when IsEndOfWord is true.

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