Longest Word in Dictionary Using Trie in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a word into the Trie.

DSA C#

public void Insert(string word) {
    TrieNode node = root;
    foreach (char c in word) {
        if (!node.Children.ContainsKey(c)) {
            node.Children.Add(c, new TrieNode());
        }
        node = node[1];
    }
    node.IsWord = true;
}

Drag options to blanks, or click blank then click option'

AChildren.ContainsKey(c)

BChildren.Add(c, new TrieNode())

CChildren[c]

DIsWord

Attempts:

3 left

💡 Hint

Common Mistakes

Using Children.Add again instead of accessing the child node.

Checking ContainsKey instead of accessing the child node.

We move to the child node corresponding to character c by accessing node.Children[c].

2fill in blank

medium

Complete the code to check if a word exists in the Trie.

DSA C#

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[1];
}

Drag options to blanks, or click blank then click option'

AIsWord

BChildren.ContainsKey(c)

CChildren[c]

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Returning true without checking if the node is a word end.

Trying to access Children[c] after the loop.

After traversing all characters, we check if the node marks the end of a valid word using IsWord.

3fill in blank

hard

Fix the error in the DFS method to find the longest word built one character at a time.

DSA C#

private void DFS(TrieNode node, string currentWord) {
    if (node == null) return;
    if (currentWord.Length > longestWord.Length) {
        longestWord = currentWord;
    }
    foreach (var pair in node.Children) {
        if (pair.Value[1]) {
            DFS(pair.Value, currentWord + pair.Key);
        }
    }
}

Drag options to blanks, or click blank then click option'

AChildren.ContainsKey(pair.Key)

BIsWord

CChildren[pair.Key]

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Checking Children.ContainsKey instead of IsWord.

Not checking if the child node is a word before DFS.

We only continue DFS if the child node marks the end of a valid word, so we check IsWord.

4fill in blank

hard

Fill both blanks to build the dictionary comprehension that filters words with all prefixes present.

DSA C#

var validWords = words.Where(word => word.All(c => trie.Search(word[1]))).ToList();

Drag options to blanks, or click blank then click option'

ASubstring(0, word.IndexOf(c) + 1)

BSubstring(0, word.IndexOf(c))

CSubstring(0, word.Length)

DSubstring(1)

Attempts:

3 left

💡 Hint

Common Mistakes

Using Substring with wrong indices causing empty or wrong prefixes.

Not including the current character in the prefix.

We check if all prefixes from start to current character index + 1 exist in the trie using Substring(0, index+1).

5fill in blank

hard

Fill all three blanks to complete the method that finds the longest word using DFS on the Trie.

DSA C#

public string LongestWord(string[] words) {
    foreach (var word in words) {
        trie[1](word);
    }
    longestWord = "";
    DFS(trie[2], "");
    return longestWord;
}

private void DFS(TrieNode node, string currentWord) {
    if (node == null) return;
    if (currentWord.Length > longestWord.Length || (currentWord.Length == longestWord.Length && string.Compare(currentWord, longestWord) < 0)) {
        longestWord = currentWord;
    }
    foreach (var pair in node.Children.OrderBy(p => p.Key)) {
        if (pair.Value[3]) {
            DFS(pair.Value, currentWord + pair.Key);
        }
    }
}

Drag options to blanks, or click blank then click option'

AInsert

Broot

CIsWord

DSearch

Attempts:

3 left

💡 Hint

Common Mistakes

Calling Search instead of Insert when adding words.

Starting DFS from a wrong node.

Not checking IsWord before DFS recursion.

We insert each word into the trie, start DFS from root, and continue DFS only if child node IsWord is true.

Practice

1. What is the main purpose of using a Trie data structure when finding the longest word in a dictionary?

easy

A. To sort words alphabetically

B. To efficiently store and search words by their prefixes

C. To count the total number of words

D. To reverse the words in the dictionary

Solution

1. Step 1: Understand Trie structure

   A Trie stores words by sharing common prefixes, making prefix searches fast.

2. Step 2: Relate to longest word search

   Finding the longest word with all prefixes present is easier using Trie traversal.

3. Final Answer:

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

4. Quick Check:

   Trie = prefix search [OK]

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

Common Mistakes:

• Confusing Trie with sorting algorithms
• Thinking Trie reverses words
• Assuming Trie counts words only

2. Which of the following is the correct way to declare a Trie node class in C# for storing children nodes?

easy

A. public class TrieNode { public Dictionary Children = new Dictionary(); public bool IsWord = false; }

B. public class TrieNode { public List<char> Children; public bool IsWord; }

C. public class TrieNode { public char[] Children = new char[26]; public bool IsWord; }

D. public class TrieNode { public int ChildrenCount; public bool IsWord; }

Solution

1. Step 1: Check children storage type

   Using a Dictionary allows dynamic children mapping by character.

2. Step 2: Confirm boolean flag for word end

   IsWord marks if node completes a valid word.

3. Final Answer:

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

4. Quick Check:

   Dictionary + IsWord = correct TrieNode [OK]

Hint: Use Dictionary for flexible children [OK]

Common Mistakes:

• Using List<char> instead of mapping to nodes
• Using char array without node references
• Missing IsWord flag

3. Given the following code snippet, what will be the output?

var words = new string[] {"a", "app", "ap", "apply", "apple"};
var trie = new Trie();
foreach(var w in words) trie.Insert(w);
var longest = trie.FindLongestWord();
Console.WriteLine(longest);

Assuming FindLongestWord returns the longest word where all prefixes exist in the Trie.

medium

A. "ap"

B. "apply"

C. "apple"

D. "app"

Solution

1. Step 1: Insert all words into Trie

   Words inserted: "a", "app", "ap", "apply", "apple".

2. Step 2: Check prefixes for each word

   "apple" prefixes: "a", "ap", "app", "appl" ("appl" missing), so invalid.
   "apply" prefixes: "a", "ap", "app", "appl" ("appl" missing), invalid.
   "app" prefixes: "a", "ap", "app" all exist.
   "ap" prefixes: "a", "ap" exist but shorter than "app".

3. Final Answer:

   "app" -> Option D

4. Quick Check:

   Longest word with all prefixes = "app" [OK]

Hint: Check all prefixes exist for longest word [OK]

Common Mistakes:

• Assuming 'apple' or 'apply' are valid without all prefixes
• Ignoring prefix 'appl' missing
• Choosing shortest word instead

4. Identify the bug in this C# Trie insertion method snippet:

public void Insert(string word) {
  var node = root;
  foreach (char c in word) {
    if (!node.Children.ContainsKey(c))
      node.Children[c] = new TrieNode();
    node = node.Children[c];
    node.IsWord = true;
  }
}

medium

A. Setting IsWord = true inside the loop for every character

B. Not checking if root is null

C. Using foreach instead of for loop

D. Not initializing Children dictionary

Solution

1. Step 1: Analyze IsWord assignment

   IsWord should be true only at the end of the word, not for every character node.

2. Step 2: Identify correct placement

   IsWord = true must be set after the loop completes, marking the last node.

3. Final Answer:

   Setting IsWord = true inside the loop for every character -> Option A

4. Quick Check:

   IsWord only at word end [OK]

Hint: Set IsWord true only after full word insertion [OK]

Common Mistakes:

• Marking IsWord true too early
• Ignoring Children initialization
• Confusing loop types

5. You have a list of words: ["w", "wo", "wor", "worl", "world", "word", "worst"]. Using a Trie, which word will be returned as the longest word where all prefixes exist in the dictionary?

hard

A. "worst"

B. "word"

C. "world"

D. "worl"

Solution

1. Step 1: Check prefixes for each candidate

   "world" prefixes: "w", "wo", "wor", "worl", "world" all exist.
   "worst" prefixes: "w", "wo", "wor", "wors" (missing), invalid.
   "word" prefixes: "w", "wo", "wor", "word" all exist but shorter than "world".
   "worl" prefixes: "w", "wo", "wor", "worl" all exist but shorter.

2. Step 2: Choose longest valid word

   "world" is longest with all prefixes present.

3. Final Answer:

   "world" -> Option C

4. Quick Check:

   Longest word with all prefixes = "world" [OK]

Hint: Longest word with all prefixes present wins [OK]

Common Mistakes:

• Choosing 'worst' without 'wors' prefix
• Ignoring prefix checks
• Picking shorter words