Longest Word in Dictionary Using Trie in DSA C# - Time & Space Complexity

Time Complexity: Longest Word in Dictionary Using Trie

O(N * L)

Understanding Time Complexity

We want to understand how the time needed grows when finding the longest word in a dictionary using a Trie.

How does the number of steps change as the dictionary gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

public void Insert(TrieNode root, 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;
}
    

This code inserts words into a Trie, marking the end of each word.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Inserting each word character by character into the Trie.
• How many times: For each word, the loop runs once per character; for all words, this repeats for every character in the dictionary.

How Execution Grows With Input

As the dictionary grows, the total characters inserted increase, so the work grows with total characters.

Input Size (n = number of words)	Approx. Operations (total characters)
10	~50 (if average word length is 5)
100	~500
1000	~5000

Pattern observation: The operations grow roughly in proportion to the total number of characters across all words.

Final Time Complexity

Time Complexity: O(N * L)

This means the time grows with the number of words (N) times the average length of each word (L).

Common Mistake

[X] Wrong: "Inserting all words is just O(N) because we only loop over words once."

[OK] Correct: Each word has multiple characters, so the inner loop over characters matters and multiplies the work.

Interview Connect

Understanding this complexity helps you explain how tries efficiently handle many words and why character-level operations matter.

Self-Check

"What if we used a hash set instead of a Trie? How would the time complexity for finding the longest word change?"

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