Trie Search Operation in DSA C# - Build from Scratch

Trie Search Operation

📖 Scenario: Imagine you are building a simple search feature for a phone contact list. You want to quickly check if a contact name exists in your list using a special tree called a Trie.

🎯 Goal: Build a Trie data structure and implement a search operation to check if a given contact name is present in the Trie.

📋 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 Insert and Search methods

Insert given contact names into the Trie

Search for a specific contact name in the Trie and print if it exists

💡 Why This Matters

🌍 Real World

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

💼 Career

Understanding Trie operations is useful for software engineers working on text processing, search optimization, and data indexing.

1

Create TrieNode class and initialize root

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 and Trie class with Root node
// Your code here

Hint

Think of TrieNode as a box holding letters and a flag if a word ends there. The Trie has a root box to start from.

2

Add Insert method to Trie

Inside 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;
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 below
    // 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

Inside 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;
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 below
    // 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 contacts and search for a name

Create a Trie object called contactsTrie. Insert the contact names "Alice", "Bob", and "Charlie" into contactsTrie using the Insert method. Then search for the name "Bob" using the Search method. Print "Found" if the search returns true, 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;
    }
}

class Program
{
    static void Main()
    {
        // Create Trie and insert contacts
        // Search for "Bob" and print result
        // Your code here
    }
}

Hint

Insert each contact name using Insert. Then search for "Bob" and print "Found" if true, else "Not Found".

Practice

1. What does the Search operation in a Trie data structure do?

easy

A. Checks if a given word exists in the Trie

B. Inserts a new word into the Trie

C. Deletes a word from the Trie

D. Counts the total words stored in the Trie

Solution

1. Step 1: Understand the purpose of Search in Trie

   The Search operation is designed to check if a specific word is present in the Trie data structure.

2. Step 2: Differentiate from other operations

   Insertion adds words, deletion removes words, and counting totals words. Search only checks existence.

3. Final Answer:

   Checks if a given word exists in the Trie -> Option A

4. Quick Check:

   Search = Check word presence [OK]

Hint: Search checks presence, not insertion or deletion [OK]

Common Mistakes:

• Confusing search with insert operation
• Thinking search deletes words
• Assuming search counts words

2. Which of the following is the correct C# method signature for a Trie search operation that returns a boolean?

easy

A. public void Search(string word)

B. public bool Search(string word)

C. public int Search(string word)

D. public string Search(string word)

Solution

1. Step 1: Identify return type for search

   Search should return true or false indicating if the word exists, so return type must be bool.

2. Step 2: Check method signature correctness

   Method takes a string parameter for the word and returns bool, matching "public bool Search(string word)".

3. Final Answer:

   public bool Search(string word) -> Option B

4. Quick Check:

   Search returns bool for word presence [OK]

Hint: Search returns true/false, so return type is bool [OK]

Common Mistakes:

• Using void return type for search
• Returning int or string instead of bool
• Incorrect method parameter types

3. Given the following Trie search code snippet, what will be the output when searching for the word "cat" after inserting "car" and "cat"?

Trie trie = new Trie();
trie.Insert("car");
trie.Insert("cat");
Console.WriteLine(trie.Search("cat"));
Console.WriteLine(trie.Search("cap"));

medium

A. False
True

B. True
True

C. True
False

D. False
False

Solution

1. Step 1: Analyze inserted words

   Words "car" and "cat" are inserted, so both exist in the Trie.

2. Step 2: Check search results for "cat" and "cap"

   "cat" exists, so search returns true; "cap" was not inserted, so search returns false.

3. Final Answer:

   True False -> Option C

4. Quick Check:

   Search("cat")=True, Search("cap")=False [OK]

Hint: Inserted words return true; others return false [OK]

Common Mistakes:

• Assuming "cap" exists after inserting "car" and "cat"
• Mixing output order
• Confusing true/false outputs

4. Identify the bug in this Trie search method that causes it to always return false:

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

medium

A. The method should return true immediately after first character check

B. It should return false if node.Children contains the character

C. The foreach loop should iterate over node.Children keys

D. It should return true after checking all characters if node marks end of word

Solution

1. Step 1: Understand the search logic

   The method checks each character in the word exists in the Trie nodes.

2. Step 2: Identify the missing return condition

   After the loop, it always returns false instead of checking if the current node marks the end of a valid word.

3. Final Answer:

   It should return true after checking all characters if node marks end of word -> Option D

4. Quick Check:

   Return true if end of word reached [OK]

Hint: Return true only if end of word node reached [OK]

Common Mistakes:

• Returning false unconditionally after loop
• Not checking end of word flag
• Returning true too early

5. You want to modify a Trie search operation to support prefix search (checking if any word starts with a given prefix). Which change is correct?

hard

A. Return true as soon as all prefix characters are found, without checking end of word

B. Return true only if the prefix is also a complete word in the Trie

C. Return false if any character in prefix is found

D. Return true only if prefix length equals word length

Solution

1. Step 1: Understand prefix search goal

   Prefix search should confirm if the Trie contains any word starting with the given prefix.

2. Step 2: Adjust search logic for prefix

   Return true immediately after all prefix characters are found, no need to check if prefix is a complete word.

3. Final Answer:

   Return true as soon as all prefix characters are found, without checking end of word -> Option A

4. Quick Check:

   Prefix found = true without full word check [OK]

Hint: Prefix search returns true once prefix path exists [OK]

Common Mistakes:

• Checking end of word for prefix search
• Returning false if prefix is not a full word
• Confusing prefix search with full word search