Longest Word in Dictionary Using Trie in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Longest Word Found Using Trie

What is the output of the following C# code that builds a Trie from a list of words and finds the longest word where every prefix is also a word in the list?

DSA C#

using System;
using System.Collections.Generic;

class TrieNode {
    public TrieNode[] children = new TrieNode[26];
    public bool isWord = false;
}

class Trie {
    private TrieNode root = new TrieNode();

    public void Insert(string word) {
        TrieNode node = root;
        foreach (char c in word) {
            int index = c - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isWord = true;
    }

    public string LongestWord() {
        string result = "";
        DFS(root, "", ref result);
        return result;
    }

    private void DFS(TrieNode node, string path, ref string result) {
        if (node == null) return;
        if (path.Length > result.Length || (path.Length == result.Length && string.Compare(path, result) < 0)) {
            result = path;
        }
        for (int i = 0; i < 26; i++) {
            if (node.children[i] != null && node.children[i].isWord) {
                DFS(node.children[i], path + (char)(i + 'a'), ref result);
            }
        }
    }
}

class Program {
    static void Main() {
        string[] words = {"a", "app", "ap", "apply", "apple", "appl"};
        Trie trie = new Trie();
        foreach (string w in words) {
            trie.Insert(w);
        }
        Console.WriteLine(trie.LongestWord());
    }
}

A "app"

B "apply"

C "apple"

D "appl"

💡 Hint

Check which words have all prefixes present in the list and compare their lengths.

The code inserts all words into the Trie and then uses DFS to find the longest word where every prefix is also a word. "apple" is the longest such word because all prefixes "a", "ap", "app", "appl" are present and marked as words.

🧠 Conceptual

intermediate

Understanding Trie Node Structure

In the context of implementing a Trie for the longest word problem, what does the boolean field 'isWord' in each Trie node represent?

A It indicates whether the node represents the end of a valid word inserted in the Trie.

B It counts how many words pass through this node.

C It stores the character value of the node.

D It marks if the node has any children nodes.

💡 Hint

Think about how the Trie distinguishes complete words from prefixes.

The 'isWord' boolean marks if the path from root to this node forms a complete word inserted in the Trie. This helps to verify if prefixes are valid words.

🔧 Debug

advanced

Identify the Bug in Trie DFS Method

What error will occur when running this DFS method in the Trie class to find the longest word, and why? private void DFS(TrieNode node, string path, ref string result) { if (node == null) return; if (path.Length > result.Length || (path.Length == result.Length && string.Compare(path, result) < 0)) { result = path; } for (int i = 0; i <= 26; i++) { if (node.children[i] != null && node.children[i].isWord) { DFS(node.children[i], path + (char)(i + 'a'), ref result); } } }

A NullReferenceException because node.children[i] might be null.

B IndexOutOfRangeException because the loop goes from 0 to 26 inclusive, exceeding array bounds.

C StackOverflowException due to infinite recursion.

D No error; the code runs correctly.

💡 Hint

Check the loop boundary condition for array indexing.

The children array has size 26 indexed 0 to 25. Looping with i <= 26 tries to access index 26, causing IndexOutOfRangeException.

🚀 Application

advanced

Longest Word with All Prefixes Present

Given the list of words ["w", "wo", "wor", "worl", "world", "banana", "ban", "bana", "banan"], which word will the Trie-based algorithm return as the longest word where every prefix is also a word?

A "worl"

B "banana"

C "banan"

D "world"

💡 Hint

Check which words have all prefixes present in the list.

"world" is the longest word where all prefixes "w", "wo", "wor", "worl" are present. "banana" is missing some prefixes like "banan" is present but "banana" itself is not fully validated by prefixes.

🧠 Conceptual

expert

Why Use DFS in Trie for Longest Word?

Why is Depth-First Search (DFS) the preferred method to find the longest word in a Trie where every prefix is also a word?

A DFS explores each path fully, allowing verification of all prefixes before choosing the longest valid word.

B DFS uses less memory than Breadth-First Search (BFS) in all cases.

C DFS automatically sorts words lexicographically without extra code.

D DFS avoids recursion and uses iteration, making it faster.

💡 Hint

Consider how DFS explores paths and checks conditions along the way.

DFS explores each branch fully, so it can check if all prefixes are valid words before updating the longest word found. BFS would require additional checks and bookkeeping.

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