Prefix Search Using Trie in DSA C# - Build from Scratch

Prefix Search Using Trie

📖 Scenario: You are building a simple search feature for a phone contact list. When a user types the first few letters of a name, the app should quickly find all contacts starting with those letters.

🎯 Goal: Create a Trie data structure to store contact names and implement a prefix search to find all contacts starting with a given prefix.

📋 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 methods to insert words and search for all words starting with a prefix

Insert a fixed list of contact names into the Trie

Search for contacts starting with a given prefix and print the results

💡 Why This Matters

🌍 Real World

Prefix search is used in search engines, contact lists, and autocomplete features to quickly find matching words or names.

💼 Career

Understanding Trie and prefix search is useful for software engineers working on search functionality, text processing, and user interface features.

1

Create TrieNode class and Trie class with Insert method

Create a class called TrieNode with a public dictionary called Children of type Dictionary and a public boolean called IsEndOfWord. Then create a class called Trie with a public TrieNode field called Root initialized in the constructor. Add a method Insert(string word) in Trie that inserts the given word into the Trie.

DSA C#

// Your code here

Hint

Use a dictionary to store children nodes for each character. Mark the end of a word with a boolean.

2

Insert contact names into the Trie

Create a list of strings called contacts with these exact names: "Alice", "Bob", "Alfred", "Bobby", "Alex". Then create a Trie object called trie and insert each contact from contacts into trie using the Insert method.

DSA C#

using System;
using System.Collections.Generic;

// Insert the contacts into the trie below
// Your code here

Hint

Use a list to hold the contact names and a foreach loop to insert each into the trie.

3

Add method to search all words starting with a prefix

In the Trie class, add a public method List SearchByPrefix(string prefix) that returns a list of all words in the Trie starting with prefix. Use a helper method void DFS(TrieNode node, string currentWord, List results) to collect words by depth-first search from the node reached after following the prefix.

DSA C#

using System;
using System.Collections.Generic;

// Add SearchByPrefix and DFS methods inside Trie class
// Your code here

Hint

Follow the prefix characters to reach the node, then use DFS to find all words below it.

4

Print all contacts starting with a given prefix

In the Main method, call SearchByPrefix on trie with the prefix "Al" and store the result in a variable called results. Then print each contact in results on its own line.

DSA C#

using System;
using System.Collections.Generic;

// Call SearchByPrefix with "Al" and print each result
// Your code here

Hint

Call SearchByPrefix with "Al" and print each contact on its own line.

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