Word Search in Trie in DSA C#

Mental Model

A trie stores words by sharing common prefixes, so searching a word means following the path of its letters in the trie.

Analogy: Imagine a tree of roads where each road sign is a letter. To find a word, you follow the signs letter by letter until you reach the end of the word.

root
 ↓
 [c] -> [a] -> [t*]
        ↓
       [r] -> [e] -> [t*]

* means end of a word

Dry Run Walkthrough

Input: Insert words: cat, car, care; Search word: care

Goal: Find if the word 'care' exists in the trie

Step 1: Start at root, check for 'c'

root -> [c] -> ...

Why: We must find the first letter 'c' to start the search path

Step 2: Move to node 'a' after 'c'

root -> c -> [a] -> ...

Why: Next letter 'a' must be found after 'c'

Step 3: Move to node 'r' after 'a'

root -> c -> a -> [r] -> ...

Why: Next letter 'r' must be found after 'a'

Step 4: Move to node 'e' after 'r'

root -> c -> a -> r -> [e*]

Why: Next letter 'e' must be found and it marks end of word

Result:

root -> c -> a -> r -> e* (word 'care' found)

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

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 ch in word)
        {
            if (!node.Children.ContainsKey(ch))
                node.Children[ch] = new TrieNode();
            node = node.Children[ch]; // advance node to child
        }
        node.IsEndOfWord = true; // mark end of word
    }

    public bool Search(string word)
    {
        TrieNode node = root;
        foreach (char ch in word)
        {
            if (!node.Children.ContainsKey(ch))
                return false; // letter missing, word not found
            node = node.Children[ch]; // advance node to child
        }
        return node.IsEndOfWord; // check if end of word
    }
}

public class Program
{
    public static void Main()
    {
        Trie trie = new Trie();
        trie.Insert("cat");
        trie.Insert("car");
        trie.Insert("care");

        Console.WriteLine(trie.Search("care") ? "Found" : "Not Found");
    }
}

node = node.Children[ch]; // advance node to child

advance node to next letter node to follow the word path

node.IsEndOfWord = true; // mark end of word

mark the last node as end of a valid word

if (!node.Children.ContainsKey(ch)) return false; // letter missing, word not found

stop search if next letter node does not exist

return node.IsEndOfWord; // check if end of word

confirm the word ends exactly here, not just prefix

Output

Found

Complexity Analysis

Time: O(m) because we check each of the m letters of the word once during search

Space: O(n*m) where n is number of words and m is average length, for storing all nodes

vs Alternative: Compared to searching in a list of words (O(n*m)), trie search is faster as it avoids checking all words

Edge Cases

Search for empty string

Returns false because empty word is not inserted

DSA C#

return node.IsEndOfWord; // check if end of word

Search for word not inserted but prefix exists (e.g., 'carp')

Returns false because 'p' node does not exist

DSA C#

if (!node.Children.ContainsKey(ch)) return false; // letter missing, word not found

Insert duplicate word

No error, trie nodes reused, end marker remains true

DSA C#

node.IsEndOfWord = true; // mark end of word

When to Use This Pattern

When you need to quickly check if words or prefixes exist in a large set, use a trie to follow letter paths efficiently.

Common Mistakes

Mistake: Not marking the end of word node, causing search to return true for prefixes
Fix: Set IsEndOfWord = true at the last node of inserted word

Mistake: Returning true if prefix exists without checking end of word
Fix: Check node.IsEndOfWord after traversing all letters

Summary

Stores words by shared letter paths and checks if a word exists by following those paths.

Use when you want fast word or prefix search among many words.

The key is to follow each letter node and confirm the word ends exactly at the last letter.

Practice

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

easy

A. To efficiently store and search words by their prefixes

B. To sort words alphabetically

C. To store words in a linked list

D. To perform arithmetic operations on words

Solution

1. Step 1: Understand Trie structure

   A Trie stores characters of words in a tree-like structure where each node represents a character.

2. Step 2: Identify Trie usage in word search

   It allows quick prefix-based search, making it efficient to find words starting with given letters.

3. Final Answer:

   To efficiently store and search words by their prefixes -> Option A

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie is best for prefix-based word searches [OK]

Common Mistakes:

• Confusing Trie with sorting structures
• Thinking Trie stores words linearly
• Assuming Trie is for arithmetic

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 IsWordEnd = false; }

B. public class TrieNode { public List<int> Children; public bool IsWordEnd; }

C. public class TrieNode { public string Children; public int IsWordEnd; }

D. public class TrieNode { public int Children; public bool IsWordEnd; }

Solution

1. Step 1: Check data types for children

   Trie children should map characters to TrieNode objects, so Dictionary is correct.

2. Step 2: Check word end marker

   Boolean flag IsWordEnd indicates if node ends a word, so bool is correct type.

3. Final Answer:

   public class TrieNode { public Dictionary Children = new Dictionary(); public bool IsWordEnd = false; } -> Option A

4. Quick Check:

   Children dictionary + bool flag = public class TrieNode { public Dictionary Children = new Dictionary(); public bool IsWordEnd = false; } [OK]

Hint: Trie node children map chars to nodes with bool end flag [OK]

Common Mistakes:

• Using List<int> instead of Dictionary
• Using string or int for children
• Using int instead of bool for IsWordEnd

3. Given the following C# code snippet for searching a word in a Trie, what will be the output?

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

bool result = trie.Search("cap");
Console.WriteLine(result);

medium

A. True

B. False

C. Compilation error

D. Runtime exception

Solution

1. Step 1: Understand inserted words

   Words "cat", "car", and "dog" are inserted into the Trie.

2. Step 2: Search for "cap"

   "cap" shares prefix "ca" but 'p' is not inserted after 'a', so search returns false.

3. Final Answer:

   False -> Option B

4. Quick Check:

   Word not found = False [OK]

Hint: Search returns false if full word path missing [OK]

Common Mistakes:

• Assuming prefix match means word found
• Expecting true for partial matches
• Confusing compilation/runtime errors

4. Identify the error in the following C# Trie search method:

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

medium

A. It does not check for null root

B. It throws NullReferenceException if word is empty

C. It returns true even if the word is only a prefix, not a complete word

D. It uses wrong data type for node

Solution

1. Step 1: Analyze search logic

   The method checks if all characters exist in Trie nodes but does not check if last node marks end of a word.

2. Step 2: Identify missing condition

   Without checking node.IsWordEnd, it returns true for prefixes that are not complete words.

3. Final Answer:

   It returns true even if the word is only a prefix, not a complete word -> Option C

4. Quick Check:

   Missing IsWordEnd check = It returns true even if the word is only a prefix, not a complete word [OK]

Hint: Always check IsWordEnd after traversal [OK]

Common Mistakes:

• Ignoring IsWordEnd flag
• Assuming prefix means word found
• Not handling empty strings

5. You want to find all words in a Trie that start with the prefix "pre". Which approach correctly uses the Trie to achieve this?

hard

A. Use a hash set to store all words and filter those starting with "pre"

B. Search each word in the Trie individually to check if it starts with "pre"

C. Insert all words starting with "pre" into a new Trie and search there

D. Traverse the Trie to the node representing 'e' in "pre", then perform a DFS to collect all words below

Solution

1. Step 1: Locate prefix node in Trie

   Traverse characters 'p', 'r', 'e' to reach the node representing last prefix character.

2. Step 2: Collect words using DFS

   From this node, perform depth-first search to find all complete words that start with "pre".

3. Final Answer:

   Traverse the Trie to the node representing 'e' in "pre", then perform a DFS to collect all words below -> Option D

4. Quick Check:

   Prefix node + DFS = Traverse the Trie to the node representing 'e' in "pre", then perform a DFS to collect all words below [OK]

Hint: Find prefix node, then DFS for words [OK]

Common Mistakes:

• Checking all words individually
• Using unrelated data structures
• Rebuilding Trie unnecessarily