Trie Insert Operation in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after inserting words into a Trie?

Consider a Trie where we insert the words "cat", "car", and "dog" in this order. What is the printed structure of the Trie after these insertions?

DSA C#

public class TrieNode {
    public Dictionary<char, TrieNode> Children = new Dictionary<char, TrieNode>();
    public bool IsEndOfWord = false;
}

public class Trie {
    private TrieNode root = new TrieNode();

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

    public void PrintTrie() {
        PrintNode(root, "");
    }

    private void PrintNode(TrieNode node, string prefix) {
        if (node.IsEndOfWord) {
            Console.WriteLine(prefix);
        }
        foreach (var child in node.Children) {
            PrintNode(child.Value, prefix + child.Key);
        }
    }
}

var trie = new Trie();
trie.Insert("cat");
trie.Insert("car");
trie.Insert("dog");
trie.PrintTrie();

A ["cat", "dog"]

B ["cat", "car"]

C ["car", "dog"]

D ["cat", "car", "dog"]

💡 Hint

Think about how each word is stored in the Trie and when the end of a word is marked.

The Trie stores all inserted words. After inserting "cat", "car", and "dog", all three words are present and printed because each insertion marks the end of the word.

❓ Predict Output

intermediate

What is the output after inserting overlapping prefixes in a Trie?

Given the following insertions into an empty Trie: "bat", "bath", "baton", what words will be printed by the PrintTrie method?

DSA C#

public class TrieNode {
    public Dictionary<char, TrieNode> Children = new Dictionary<char, TrieNode>();
    public bool IsEndOfWord = false;
}

public class Trie {
    private TrieNode root = new TrieNode();

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

    public void PrintTrie() {
        PrintNode(root, "");
    }

    private void PrintNode(TrieNode node, string prefix) {
        if (node.IsEndOfWord) {
            Console.WriteLine(prefix);
        }
        foreach (var child in node.Children) {
            PrintNode(child.Value, prefix + child.Key);
        }
    }
}

var trie = new Trie();
trie.Insert("bat");
trie.Insert("bath");
trie.Insert("baton");
trie.PrintTrie();

A ["bat", "bath", "baton"]

B ["bat", "bath"]

C ["bath", "baton"]

D ["baton"]

💡 Hint

Remember that each word insertion marks the end of the word even if prefixes overlap.

All three words are inserted and marked as complete words in the Trie. The PrintTrie method prints all words where IsEndOfWord is true.

❓ Predict Output

advanced

What is the output after inserting words with shared prefixes and printing in lex order?

After inserting "apple", "app", "application" into a Trie, what is the order of words printed by the PrintTrie method that prints words in lexicographical order?

DSA C#

public class TrieNode {
    public SortedDictionary<char, TrieNode> Children = new SortedDictionary<char, TrieNode>();
    public bool IsEndOfWord = false;
}

public class Trie {
    private TrieNode root = new TrieNode();

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

    public void PrintTrie() {
        PrintNode(root, "");
    }

    private void PrintNode(TrieNode node, string prefix) {
        if (node.IsEndOfWord) {
            Console.WriteLine(prefix);
        }
        foreach (var child in node.Children) {
            PrintNode(child.Value, prefix + child.Key);
        }
    }
}

var trie = new Trie();
trie.Insert("apple");
trie.Insert("app");
trie.Insert("application");
trie.PrintTrie();

A ["app", "application", "apple"]

B ["app", "apple", "application"]

C ["application", "apple", "app"]

D ["apple", "app", "application"]

💡 Hint

The Trie uses a sorted dictionary for children, so words print in alphabetical order.

The words print in lexicographical order: "app" (shortest prefix), then "apple", then "application".

🔧 Debug

advanced

Identify the error in this Trie insert method

What error will occur when running this insert method in a Trie implementation?

DSA C#

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

A Syntax error due to missing semicolon

B NullReferenceException because node is never initialized

C The code overwrites existing children nodes causing loss of data

D No error, code runs correctly

💡 Hint

Check the condition inside the if statement and what happens when it is true.

The condition incorrectly creates a new node when the child already exists, overwriting it and losing previous data.

🧠 Conceptual

expert

What is the time complexity of inserting a word of length n into a Trie?

Assuming a Trie is implemented with a hash map or dictionary for children nodes, what is the time complexity to insert a word of length n?

A O(n), where n is the length of the word

B O(1), constant time regardless of word length

C O(n^2), quadratic time due to nested loops

D O(log n), logarithmic time due to dictionary lookups

💡 Hint

Consider how many characters you process and how many dictionary lookups happen.

Each character is processed once, and dictionary lookups are average O(1), so total time is O(n).

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