Word Search in Trie in DSA C# - Build from Scratch

Word Search in Trie

📖 Scenario: Imagine you are building a simple word search tool that can quickly check if a word exists in a dictionary. To do this efficiently, you will use a Trie data structure, which stores words in a tree-like form.

🎯 Goal: You will create a Trie, add some words to it, and then search for a specific word to see if it exists in the Trie.

📋 What You'll Learn

Create a TrieNode class with a dictionary for children and a boolean to mark the end of a word

Create a Trie class with methods to insert words and search for a word

Insert given words into the Trie

Search for a specific word and print whether it exists or not

💡 Why This Matters

🌍 Real World

Tries are used in autocomplete features, spell checkers, and word games to quickly find words or prefixes.

💼 Career

Understanding Tries helps in roles involving search engines, text processing, and efficient data retrieval.

1

Create TrieNode and Trie classes

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 variable called Root initialized in the constructor.

DSA C#

// Define TrieNode class
// Define Trie class with Root node
// Your code here

Hint

Think of TrieNode as a box that can hold letters and mark if a word ends there. The Trie has a root box to start from.

2

Add Insert method to Trie

In the Trie class, add a public method called Insert that takes a string parameter word. Use a variable current starting at Root. For each character in word, if it is not in current.Children, add a new TrieNode. Move current to the child node. After the loop, set current.IsEndOfWord to true.

DSA C#

using System.Collections.Generic;

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

public class Trie
{
    public TrieNode Root;

    public Trie()
    {
        Root = new TrieNode();
    }

    // Add Insert method here
    // Your code here
}

Hint

Think of walking down the tree for each letter. If a letter path is missing, create it. Mark the end of the word at the last letter.

3

Add Search method to Trie

In the Trie class, add a public method called Search that takes a string parameter word and returns a boolean. Use a variable current starting at Root. For each character in word, if it is not in current.Children, return false. Otherwise, move current to the child node. After the loop, return current.IsEndOfWord.

DSA C#

using System.Collections.Generic;

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

public class Trie
{
    public TrieNode Root;

    public Trie()
    {
        Root = new TrieNode();
    }

    public void Insert(string word)
    {
        TrieNode current = Root;
        foreach (char c in word)
        {
            if (!current.Children.ContainsKey(c))
            {
                current.Children[c] = new TrieNode();
            }
            current = current.Children[c];
        }
        current.IsEndOfWord = true;
    }

    // Add Search method here
    // Your code here
}

Hint

Walk down the tree for each letter. If a letter path is missing, the word is not found. At the end, check if the word ends here.

4

Insert words and search for a word

Create a Trie object called trie. Insert the words "apple", "app", and "bat" into trie using the Insert method. Then search for the word "app" using the Search method. Print "Found" if the word exists, otherwise print "Not Found".

DSA C#

using System;
using System.Collections.Generic;

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

public class Trie
{
    public TrieNode Root;

    public Trie()
    {
        Root = new TrieNode();
    }

    public void Insert(string word)
    {
        TrieNode current = Root;
        foreach (char c in word)
        {
            if (!current.Children.ContainsKey(c))
            {
                current.Children[c] = new TrieNode();
            }
            current = current.Children[c];
        }
        current.IsEndOfWord = true;
    }

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

// Create Trie object, insert words, search for "app", and print result
// Your code here

Hint

Remember to create the Trie, insert the exact words, then search for "app" and print "Found" or "Not Found" accordingly.

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