Word Search in Trie in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Trie Word Search

What is the output of the following C# code that inserts words into a Trie and searches for a specific word?

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

    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 node.IsWordEnd;
    }
}

class Program {
    static void Main() {
        Trie trie = new Trie();
        trie.Insert("apple");
        trie.Insert("app");
        trie.Insert("application");
        Console.WriteLine(trie.Search("app"));
        Console.WriteLine(trie.Search("appl"));
        Console.WriteLine(trie.Search("apple"));
    }
}

A True\nFalse\nTrue

B True\nTrue\nTrue

C False\nFalse\nTrue

D False\nTrue\nFalse

💡 Hint

Remember that Search returns true only if the word ends exactly at a node marked as word end.

The word "app" is inserted and marked as a word end, so Search("app") returns true. "appl" is a prefix but not a word end, so Search("appl") returns false. "apple" is inserted and marked as word end, so Search("apple") returns true.

❓ Predict Output

intermediate

Trie Search Result for Non-Inserted Word

Given the following Trie insertions, what will be the output of searching for the word "bat"?

DSA C#

Trie trie = new Trie();
trie.Insert("batman");
trie.Insert("batch");
trie.Insert("bath");
Console.WriteLine(trie.Search("bat"));

A False

B True

C Throws NullReferenceException

D Compilation Error

💡 Hint

Check if "bat" was inserted as a complete word or only as a prefix.

"bat" is a prefix of inserted words but was never inserted as a complete word, so Search returns false.

🔧 Debug

advanced

Identify the Bug in Trie Search Method

What error will the following Trie Search method cause when searching for a word not present in the Trie?

DSA C#

public bool Search(string word) {
    TrieNode node = root;
    foreach (char c in word) {
        node = node.Children[c];
    }
    return node.IsWordEnd;
}

A No error, works correctly

B NullReferenceException

C KeyNotFoundException

D Returns false incorrectly

💡 Hint

What happens if the character key does not exist in the dictionary?

Accessing node.Children[c] without checking if c exists causes a KeyNotFoundException if c is missing.

🧠 Conceptual

advanced

Trie Node Memory Usage

Which of the following statements about memory usage in a Trie node is correct?

A Each Trie node stores a fixed-size array of 26 children regardless of inserted words.

B Trie nodes store the entire word they represent to save memory.

C Trie nodes store only the character they represent and no children references.

D Each Trie node stores a dictionary mapping characters to child nodes, using memory proportional to actual children.

💡 Hint

Consider how children are stored to optimize memory for sparse tries.

Using a dictionary for children stores only existing child nodes, saving memory compared to fixed arrays.

🚀 Application

expert

Longest Word with All Prefixes in Trie

Given a list of words inserted into a Trie, which approach correctly finds the longest word such that all its prefixes are also present in the Trie?

A Sort words by length descending and check each word's prefixes in the Trie using Search method, return first found.

B Perform DFS on Trie nodes, collecting words where each prefix node is marked as word end, track longest word found.

C Insert all words, then perform BFS on Trie nodes ignoring word end flags, return longest path found.

D Use a hash set of words and check prefixes without Trie traversal, return longest word with all prefixes.

💡 Hint

Think about how to verify all prefixes exist efficiently using Trie structure.

DFS on Trie nodes checking word end flags ensures all prefixes exist, allowing to find longest valid word.

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