Longest Word in Dictionary Using Trie in DSA C#

Mental Model

We build a tree where each path from root to a node forms a word prefix. We find the longest word where every prefix is also a word.

Analogy: Imagine a family tree where each generation adds one letter. We want the longest name where every smaller name before it is also in the family.

root
 ↓
 a -> p -> p -> l -> e
       ↓
       e -> null
Each arrow is a letter link forming words like 'app' and 'apple'.

Dry Run Walkthrough

Input: words = ["a", "app", "ap", "apple", "apply"]

Goal: Find the longest word where all prefixes are also words in the list.

Step 1: Insert 'a' into trie, mark node 'a' as word end

root -> a[isWord=true] -> null

Why: We start by adding the shortest word to build prefixes.

Step 2: Insert 'app' into trie, mark node 'p' (3rd letter) as word end

root -> a[isWord=true] -> p -> p[isWord=true] -> null

Why: Add 'app' only if prefixes 'a' and 'ap' exist; 'ap' not marked yet but will be added next.

Step 3: Insert 'ap' into trie, mark node 'p' (2nd letter) as word end

root -> a[isWord=true] -> p[isWord=true] -> p[isWord=true] -> null

Why: Mark 'ap' as a word so 'app' prefixes are valid.

Step 4: Insert 'apple' into trie, mark node 'e' as word end

root -> a[isWord=true] -> p[isWord=true] -> p[isWord=true] -> l -> e[isWord=true] -> null

Why: Add longer word 'apple' only if all prefixes 'a', 'ap', 'app', 'appl' are words; 'appl' not word yet.

Step 5: Insert 'apply' into trie, mark node 'y' as word end

root -> a[isWord=true] -> p[isWord=true] -> p[isWord=true] -> l -> e[isWord=true], y[isWord=true] -> null

Why: Add 'apply' similarly; 'appl' prefix missing word mark, so 'apply' prefixes invalid.

Step 6: Search trie for longest word where all prefixes are words

Check 'a', 'ap', 'app' marked; 'appl' not marked; 'apple' and 'apply' invalid

Why: Only words with all prefixes marked count; 'app' is longest valid word.

Result:

root -> a[isWord=true] -> p[isWord=true] -> p[isWord=true] -> l -> e[isWord=true], y[isWord=true] -> null
Longest word: app

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

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

public 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 longest = "";
        DFS(root, "", ref longest);
        return longest;
    }

    private void DFS(TrieNode node, string path, ref string longest)
    {
        if (node == null) return;
        if (node != root && !node.isWord) return;

        if (path.Length > longest.Length || (path.Length == longest.Length && string.Compare(path, longest) < 0))
            longest = path;

        for (int i = 0; i < 26; i++)
        {
            if (node.children[i] != null)
            {
                DFS(node.children[i], path + (char)(i + 'a'), ref longest);
            }
        }
    }
}

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

foreach (char c in word) { int index = c - 'a'; if (node.children[index] == null) node.children[index] = new TrieNode(); node = node.children[index]; }

Insert each letter node or reuse existing; move down trie to build word path

node.isWord = true;

Mark end of inserted word to recognize valid words

if (node != root && !node.isWord) return;

Stop DFS if current node is not a word end (except root) to ensure all prefixes are words

if (path.Length > longest.Length || (path.Length == longest.Length && string.Compare(path, longest) < 0)) longest = path;

Update longest word if current path is longer or lexicographically smaller when equal length

for (int i = 0; i < 26; i++) { if (node.children[i] != null) DFS(node.children[i], path + (char)(i + 'a'), ref longest); }

Recursively explore all children nodes to find longest valid word

Output

app

Complexity Analysis

Time: O(N * L) because we insert N words each of length L and DFS visits nodes once

Space: O(N * L) for trie nodes storing all words' letters

vs Alternative: Compared to sorting and checking prefixes in array (O(N log N * L)), trie offers efficient prefix checks during DFS

Edge Cases

Empty word list

Returns empty string as no words exist

DSA C#

if (node != root && !node.isWord) return;

Words with single letter only

Returns the single letter word as longest if no longer valid words

DSA C#

node.isWord = true;

Multiple words with same length and valid prefixes

Returns lexicographically smallest word among longest

DSA C#

if (path.Length > longest.Length || (path.Length == longest.Length && string.Compare(path, longest) < 0)) longest = path;

When to Use This Pattern

When asked to find the longest word with all prefixes present, use a trie to efficiently check prefixes and find the answer by DFS.

Common Mistakes

Mistake: Not checking if all prefixes are words before extending path
Fix: Add condition to stop DFS if current node is not marked as word end (except root)

Mistake: Updating longest word without lexicographical tie-break
Fix: Compare strings lex order when lengths are equal to pick smallest

Summary

Build a trie from words and find the longest word where every prefix is also a word.

Use when you need to find words with all prefixes present efficiently.

The key is to stop exploring paths where prefixes are missing and track longest valid word during DFS.

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