Prefix Search Using Trie in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a word into the Trie.

DSA C#

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

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

AChildren.Add(c, new TrieNode())

BChildren[c]

CChildren

DChildren.ContainsKey(c)

Attempts:

3 left

💡 Hint

Common Mistakes

Trying to add a new child node again instead of moving to existing child.

Using ContainsKey instead of accessing the child node.

We move to the child node corresponding to character c by accessing node.Children[c].

2fill in blank

medium

Complete the code to check if a prefix exists in the Trie.

DSA C#

public bool StartsWith(string prefix) {
    TrieNode node = root;
    foreach (char c in prefix) {
        if (!node.Children.ContainsKey(c)) {
            return false;
        }
        node = node.[1];
    }
    return true;
}

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

AChildren.Add(c, new TrieNode())

BChildren.ContainsKey(c)

CChildren

DChildren[c]

Attempts:

3 left

💡 Hint

Common Mistakes

Using ContainsKey instead of accessing the child node.

Trying to add new nodes while searching.

To move down the Trie, we access the child node for character c using node.Children[c].

3fill in blank

hard

Fix the error in the search method to correctly check if a word exists in the Trie.

DSA C#

public bool Search(string word) {
    TrieNode node = root;
    foreach (char c in word) {
        if (!node.Children.ContainsKey(c)) {
            return false;
        }
        node = node.[1];
    }
    return node.IsWord;
}

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

AChildren[c]

BChildren.ContainsKey(c)

CChildren.Add(c, new TrieNode())

DChildren

Attempts:

3 left

💡 Hint

Common Mistakes

Using ContainsKey instead of accessing the child node.

Adding new nodes during search.

We must move to the child node for each character using node.Children[c] to continue the search.

4fill in blank

hard

Fill both blanks to complete the TrieNode class constructor and initialize the children dictionary.

DSA C#

public class TrieNode {
    public Dictionary<char, TrieNode> Children;
    public bool IsWord;

    public TrieNode() {
        Children = new Dictionary<char, [1]>();
        IsWord = [2];
    }
}

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

ATrieNode

Bbool

Ctrue

Dfalse

Attempts:

3 left

💡 Hint

Common Mistakes

Using bool as dictionary value type.

Setting IsWord to true in constructor.

Children is a dictionary mapping characters to TrieNode objects, and IsWord starts as false.

5fill in blank

hard

Fill all three blanks to complete the method that returns all words in the Trie starting with a given prefix.

DSA C#

public List<string> GetWordsWithPrefix(string prefix) {
    List<string> results = new List<string>();
    TrieNode node = root;
    foreach (char c in prefix) {
        if (!node.Children.ContainsKey(c)) {
            return results;
        }
        node = node.[1];
    }
    DFS(node, prefix, results);
    return results;
}

private void DFS(TrieNode node, string word, List<string> results) {
    if (node.IsWord) {
        results.Add(word);
    }
    foreach (var pair in node.Children) {
        DFS(pair.[2], word + pair.[3], results);
    }
}

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

AChildren[c]

BKey

CValue

DChildren

Attempts:

3 left

💡 Hint

Common Mistakes

Using pair.Key as node instead of pair.Value.

Appending pair.Value instead of pair.Key to word.

We move to child node with Children[c], then in DFS use pair.Value for node and pair.Key for character.

Practice

1. What is the main purpose of using a Trie data structure in prefix search?

easy

A. To perform arithmetic operations quickly

B. To sort words alphabetically

C. To efficiently find all words that start with a given prefix

D. To store numbers in sorted order

Solution

1. Step 1: Understand the role of Trie in prefix search

   A Trie stores words in a tree-like structure where each node represents a character. This allows quick traversal to find words sharing the same prefix.

2. Step 2: Identify the main use case

   Because of this structure, Tries are mainly used to find all words starting with a given prefix efficiently.

3. Final Answer:

   To efficiently find all words that start with a given prefix -> Option C

4. Quick Check:

   Trie = prefix search efficiency [OK]

Hint: Trie nodes represent characters for fast prefix lookup [OK]

Common Mistakes:

• Confusing Trie with sorting algorithms
• Thinking Trie is for arithmetic operations
• Assuming Trie stores numbers only

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

easy

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

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 the correct data type for children nodes

   Trie nodes store children as a map from characters to TrieNode objects. Dictionary is the correct choice in C#.

2. Step 2: Check the other options

   List<int> or int[] are incorrect because they don't map characters to nodes. String is also incorrect as children must be nodes, not strings.

3. Final Answer:

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

4. Quick Check:

   Children map chars to nodes = public class TrieNode { public Dictionary<char, TrieNode> Children = new Dictionary<char, TrieNode>(); public bool IsEndOfWord; } [OK]

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

Common Mistakes:

• Using List<int> instead of Dictionary
• Using array of ints instead of nodes
• Declaring children as string

3. What will be the output of the following C# code snippet?

var trie = new Trie();
trie.Insert("cat");
trie.Insert("car");
trie.Insert("dog");
var result = trie.SearchPrefix("ca");
Console.WriteLine(string.Join(",", result));

Assuming SearchPrefix returns all words starting with the given prefix.

medium

A. cat,car

B. dog

C. cat

D. car,dog

Solution

1. Step 1: Insert words into the Trie

   The words "cat", "car", and "dog" are inserted. "cat" and "car" share the prefix "ca".

2. Step 2: Search for prefix "ca"

   Searching prefix "ca" returns all words starting with "ca", which are "cat" and "car".

3. Final Answer:

   cat,car -> Option A

4. Quick Check:

   Words with prefix "ca" = cat,car [OK]

Hint: SearchPrefix returns all words starting with given prefix [OK]

Common Mistakes:

• Returning only one word instead of all matches
• Confusing prefix "ca" with "car"
• Including words without the prefix

4. The following C# method is intended to check if a prefix exists in a Trie. What is the bug?

public bool StartsWith(string prefix) {
    var node = root;
    foreach (var ch in prefix) {
        if (!node.Children.ContainsKey(ch))
            return false;
        node = node.Children[ch];
    }
    return node.IsEndOfWord;
}

medium

A. It should return false if prefix is empty

B. It should check for null before accessing Children

C. It should use a while loop instead of foreach

D. It should return true after traversing prefix, not check IsEndOfWord

Solution

1. Step 1: Understand method purpose

   The method checks if any word in the Trie starts with the given prefix.

2. Step 2: Identify the bug in return statement

   Returning node.IsEndOfWord checks if prefix itself is a complete word, but prefix search should return true if prefix exists regardless of word end.

3. Final Answer:

   It should return true after traversing prefix, not check IsEndOfWord -> Option D

4. Quick Check:

   Prefix exists if traversal succeeds, no need to check IsEndOfWord [OK]

Hint: Prefix check returns true if traversal succeeds, ignore IsEndOfWord [OK]

Common Mistakes:

• Checking IsEndOfWord for prefix existence
• Not handling empty prefix correctly
• Using wrong loop type

5. You want to implement a method GetAllWordsWithPrefix in a Trie that returns all words starting with a given prefix. Which approach correctly combines prefix traversal and word collection?

hard

A. Return words only if prefix is a complete word in Trie

B. Traverse to prefix node, then recursively collect all words from that node

C. Collect all words in Trie, then filter those starting with prefix

D. Traverse Trie nodes randomly and collect words

Solution

1. Step 1: Traverse Trie to prefix node

   First, move down the Trie following the prefix characters to reach the node representing the last prefix character.

2. Step 2: Recursively collect all words from prefix node

   From this node, recursively explore all child nodes to collect complete words that start with the prefix.

3. Final Answer:

   Traverse to prefix node, then recursively collect all words from that node -> Option B

4. Quick Check:

   Prefix traversal + recursion = Traverse to prefix node, then recursively collect all words from that node [OK]

Hint: Find prefix node first, then gather words recursively [OK]

Common Mistakes:

• Filtering all words after collecting entire Trie
• Returning words only if prefix is a full word
• Random traversal without prefix focus