Prefix Search Using Trie in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Prefix Search Result

What is the output of the following C# code that inserts words into a Trie and searches for words with prefix "app"?

DSA C#

using System;
using System.Collections.Generic;

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

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

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

    public List<string> StartsWith(string prefix) {
        var node = root;
        foreach (var ch in prefix) {
            if (!node.Children.ContainsKey(ch)) return new List<string>();
            node = node.Children[ch];
        }
        var results = new List<string>();
        DFS(node, prefix, results);
        return results;
    }

    private void DFS(TrieNode node, string path, List<string> results) {
        if (node.IsWordEnd) results.Add(path);
        foreach (var kvp in node.Children) {
            DFS(kvp.Value, path + kvp.Key, results);
        }
    }
}

class Program {
    static void Main() {
        var trie = new Trie();
        trie.Insert("apple");
        trie.Insert("app");
        trie.Insert("application");
        trie.Insert("apt");
        var result = trie.StartsWith("app");
        Console.WriteLine(string.Join(",", result));
    }
}

A app,apple,application

B apple,application

C app,apt

D application,apple

💡 Hint

Think about which words start exactly with the prefix "app".

The code inserts four words: "apple", "app", "application", and "apt". The prefix searched is "app". The words starting with "app" are "app", "apple", and "application". The word "apt" starts with "ap" but not "app".

🧠 Conceptual

intermediate

Number of Nodes in Trie After Insertions

After inserting the words "cat", "car", "cart", and "dog" into an empty Trie, how many nodes does the Trie contain?

A 10

B 11

C 9

D 8

💡 Hint

Count shared prefixes carefully to avoid double counting nodes.

Words inserted: "cat", "car", "cart", "dog".

Shared prefix "ca" nodes are shared among "cat", "car", and "cart".

Nodes: root, 'c', 'a', 't' (for cat), 'r', 't' (for cart), 'd', 'o', 'g'. Detailed count including root: 9 nodes total.

🔧 Debug

advanced

Identify the Bug in Trie Search Method

What error will the following C# Trie search method cause when searching for a prefix not present in the Trie?

DSA C#

public bool SearchPrefix(string prefix) {
    var node = root;
    foreach (var ch in prefix) {
        node = node.Children[ch];
    }
    return true;
}

A KeyNotFoundException

B NullReferenceException

C Returns false incorrectly

D No error, returns true

💡 Hint

What happens if the character key does not exist in the dictionary?

The code accesses node.Children[ch] without checking if the key exists. If the prefix character is missing, this causes a KeyNotFoundException.

🚀 Application

advanced

Find All Words With Prefix Using Trie

Given a Trie with words inserted: "bat", "batch", "bath", "banana", "band", which of the following lists is returned by searching for prefix "ba"?

A ["batch", "bath", "band"]

B ["bat", "batch", "bath"]

C ["banana", "band"]

D ["bat", "batch", "bath", "banana", "band"]

💡 Hint

All words starting with "ba" should be included.

All inserted words start with "ba" so all are returned.

🧠 Conceptual

expert

Time Complexity of Prefix Search in Trie

What is the time complexity of searching for all words with a given prefix of length k in a Trie containing n words?

A O(log n), using binary search on sorted words

B O(k + m), where m is the number of matched words

C O(k * n), checking each word character by character

D O(n), scanning all words

💡 Hint

Consider the cost to reach the prefix node and then collect all words below it.

Searching prefix requires traversing k characters to reach the node, then DFS to collect m matched words. So complexity is O(k + m).

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