Prefix Search Using Trie in DSA C#

Mental Model

A trie stores words by sharing common starting letters, making it easy to find all words starting with a given prefix quickly.

Analogy: Imagine a tree where each branch is a letter, and paths from the root to leaves form words. To find words starting with a prefix, you just follow the branches for those letters and then collect all words below.

root
 ↓
 a -> p -> p -> l -> e [word end]
        ↓
        e -> null

Each arrow -> is a letter link, and nodes mark letters. Words end at special nodes.

Dry Run Walkthrough

Input: Insert words: "apple", "app", "ape"; then search prefix "ap"

Goal: Find all words in the trie that start with the prefix "ap"

Step 1: Insert 'apple' letter by letter into trie

root -> a -> p -> p -> l -> e [word end]

Why: Build path for 'apple' so it can be found later

Step 2: Insert 'app' sharing existing nodes for 'a', 'p', 'p', mark end at second 'p'

root -> a -> p -> p [word end] -> l -> e [word end]

Why: Reuse prefix nodes to save space and mark 'app' as a word

Step 3: Insert 'ape' sharing 'a', 'p', add new node 'e' and mark word end

root -> a -> p -> p [word end] -> l -> e [word end]
               ↓
               e [word end]

Why: Add new branch for 'ape' after 'ap'

Step 4: Search prefix 'ap' by following nodes 'a' then 'p'

At node 'p' after 'a' -> 'p'

Why: Locate the node where prefix ends to find all words below

Step 5: Collect all words below node 'p': 'app', 'apple', 'ape'

Words found: ['app', 'apple', 'ape']

Why: All words starting with 'ap' are under this node

Result:

root -> a -> p -> p [word end] -> l -> e [word end]
               ↓
               e [word end]
Words starting with 'ap': app, apple, ape

Annotated Code

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)
    {
        TrieNode curr = root;
        foreach (char c in word)
        {
            if (!curr.Children.ContainsKey(c))
                curr.Children[c] = new TrieNode();
            curr = curr.Children[c]; // advance curr to next node
        }
        curr.IsWordEnd = true; // mark end of word
    }

    public List<string> SearchPrefix(string prefix)
    {
        TrieNode curr = root;
        foreach (char c in prefix)
        {
            if (!curr.Children.ContainsKey(c))
                return new List<string>(); // prefix not found
            curr = curr.Children[c]; // advance curr to prefix end
        }
        List<string> results = new List<string>();
        DFS(curr, prefix, results); // collect all words below prefix
        return results;
    }

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

class Program
{
    static void Main()
    {
        Trie trie = new Trie();
        trie.Insert("apple");
        trie.Insert("app");
        trie.Insert("ape");

        List<string> words = trie.SearchPrefix("ap");
        Console.WriteLine("Words starting with 'ap': " + string.Join(", ", words));
    }
}

curr = curr.Children[c]; // advance curr to next node

advance curr to next node -- build or traverse path

curr.IsWordEnd = true; // mark end of word

mark current node as end of a valid word

if (!curr.Children.ContainsKey(c)) return new List<string>(); // prefix not found

stop search if prefix path breaks

DFS(curr, prefix, results); // collect all words below prefix

start depth-first search to gather all words under prefix node

if (node.IsWordEnd) results.Add(path); // found a word

add word to results when word end node reached

foreach (var kvp in node.Children) DFS(kvp.Value, path + kvp.Key, results); // explore children

recursively explore all child nodes to find words

Output

Words starting with 'ap': app, apple, ape

Complexity Analysis

Time: O(m + k) where m is length of prefix and k is total letters in all matched words because we traverse prefix nodes then collect all words below

Space: O(n) where n is total letters in all inserted words due to trie node storage

vs Alternative: Compared to scanning all words linearly (O(total words * average length)), trie reduces prefix search to O(m + k) which is faster for large datasets

Edge Cases

Empty trie (no words inserted)

Search returns empty list because prefix cannot be found

DSA C#

if (!curr.Children.ContainsKey(c)) return new List<string>(); // prefix not found

Prefix not present in trie

Search returns empty list immediately

DSA C#

if (!curr.Children.ContainsKey(c)) return new List<string>(); // prefix not found

Prefix is a complete word and also prefix to other words

Search returns all words starting with prefix including the prefix word itself

DSA C#

if (node.IsWordEnd) results.Add(path); // found a word

When to Use This Pattern

When you need to quickly find all words starting with a given prefix, use a trie because it organizes words by shared prefixes for fast lookup.

Common Mistakes

Mistake: Not marking the end of a word node, causing search to miss valid words
Fix: Set IsWordEnd = true at the last node of each inserted word

Mistake: Not checking if prefix path exists before searching deeper
Fix: Return empty list immediately if prefix node is missing during traversal

Summary

Stores words in a tree structure to enable fast prefix-based search.

Use when you want to find all words that start with a certain prefix efficiently.

The key is to follow the prefix path in the trie, then collect all words below that node.

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