Longest Word in Dictionary Using Trie in DSA C - Execution Trace

Concept Flow - Longest Word in Dictionary Using Trie

Start with empty Trie

↓

Insert each word letter by letter

↓

Mark end of word nodes

↓

Traverse Trie from root

↓

At each node, check if it ends a word

↓

If yes, continue deeper

↓

Keep track of longest word found

↓

Return longest word after traversal

Build a Trie from all words, then traverse it only through nodes that mark complete words to find the longest word.

Execution Sample

DSA C

insert("a")
insert("app")
insert("apple")
insert("apply")
longestWord = findLongestWord()

Insert words into Trie, then find the longest word where all prefixes are also words.

Execution Table

Step	Operation	Nodes in Trie	Pointer Changes	Visual State
1	Insert 'a'	Root -> a(end)	root->a created, mark end at 'a'	root └─ a*
2	Insert 'app'	Root -> a(end) -> p -> p(end)	a->p created, p->p created, mark end at last p	root └─ a* └─ p └─ p*
3	Insert 'apple'	Root -> a(end) -> p -> p(end) -> l -> e(end)	p->l created, l->e created, mark end at e	root └─ a* └─ p └─ p* └─ l └─ e*
4	Insert 'apply'	Root -> a(end) -> p -> p(end) -> l -> e(end), y(end)	l->y created, mark end at y	root └─ a* └─ p └─ p* └─ l ├─ e* └─ y*
5	Find longest word	Traverse nodes with end marks only	Traverse root->a* (update longest to 'a'), from a* child 'p' not end-of-word so stop	Longest word found: 'a'
6	End	Traversal complete	No more nodes with end marks to traverse	Return 'a'

💡 Traversal stops when no further child nodes mark end of a word.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	Final
Trie Nodes Count	1	2	4	6	7	7	7
Longest Word	""	"a"	"a"	"a"	"a"	"a"	"a"
Current Node	root	a	p	p	l	e or y	end

Key Moments - 3 Insights

Why do we only continue traversal through nodes that mark the end of a word?

Because the problem requires the longest word where all prefixes are valid words. The execution_table rows 5 and 6 show traversal stops if a node is not an end of a word.

What happens if a word is a prefix but not marked as a complete word in the Trie?

Traversal will not continue past that node, so longer words depending on that prefix won't be considered. See execution_table step 5 where only nodes with end marks are traversed.

Why do we mark nodes as 'end' during insertion?

Marking nodes as 'end' shows that a word finishes there. This is crucial for traversal to find words with all prefixes valid, as shown in execution_table steps 1-4.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, how many nodes are in the Trie after inserting 'apple'?

A 4

B 5

C 6

D 7

💡 Hint

Check the 'Nodes in Trie' column at step 3 in execution_table.

At which step does the Trie first have a node marked as end for the letter 'p'?

A Step 2

B Step 3

C Step 1

D Step 4

💡 Hint

Look at the 'Pointer Changes' and 'Visual State' columns in execution_table for when 'p' is marked end.

If the word 'app' was not inserted, how would the traversal in step 5 change?

A Traversal would continue normally

B Traversal would stop at 'a' node

C Traversal would find longer words

D Traversal would skip 'a' node

💡 Hint

Refer to key_moments about traversal only continuing through nodes marked as end.

Concept Snapshot

Build a Trie by inserting words letter by letter.
Mark nodes where words end.
Traverse Trie only through nodes marking complete words.
Keep track of longest word found during traversal.
Return longest word where all prefixes are valid words.

Full Transcript

We build a Trie by inserting each word letter by letter, marking nodes where words end. Then, we traverse the Trie starting from the root, moving only through nodes that mark the end of a word. This ensures all prefixes of the word are valid words. During traversal, we keep track of the longest word found. The traversal stops when no further child nodes mark the end of a word. Finally, we return the longest word found. This method helps find the longest word in the dictionary where every prefix is also a word.

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 count the total number of words

C. To efficiently store and search words by their prefixes

D. To reverse the words in the dictionary

Solution

1. Step 1: Understand Trie usage

   A Trie stores words by breaking them into characters and linking nodes for prefixes.

2. Step 2: Relate to longest word search

   This structure allows quick prefix checks, which helps find the longest word built from other words.

3. Final Answer:

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

4. Quick Check:

   Trie = prefix search [OK]

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

Common Mistakes:

• Thinking Trie sorts words alphabetically
• Confusing Trie with simple arrays or lists
• Assuming Trie counts words only

2. Which of the following is the correct way to declare a Trie node structure in C for lowercase English letters?

easy

A. typedef struct TrieNode { struct TrieNode* children[26]; int isEndOfWord; } TrieNode;

B. typedef struct TrieNode { struct TrieNode* children[52]; int isEndOfWord; } TrieNode;

C. typedef struct TrieNode { struct TrieNode* children[10]; int isEndOfWord; } TrieNode;

D. typedef struct TrieNode { struct TrieNode* children; int isEndOfWord; } TrieNode;

Solution

1. Step 1: Identify children array size

   Lowercase English letters are 26, so children array size must be 26.

2. Step 2: Check structure fields

   Each node has an array of pointers and a flag for word end, matching typedef struct TrieNode { struct TrieNode* children[26]; int isEndOfWord; } TrieNode;.

3. Final Answer:

   typedef struct TrieNode { struct TrieNode* children[26]; int isEndOfWord; } TrieNode; -> Option A

4. Quick Check:

   26 children for a-z [OK]

Hint: Use 26 children for lowercase letters [OK]

Common Mistakes:

• Using 52 for uppercase + lowercase without need
• Using 10 children for digits only
• Not using array for children pointers

3. Given the following code snippet inserting words into a Trie and searching for the longest word built one character at a time, what will be the output?

char* words[] = {"a", "ap", "app", "appl", "apple", "apply"};
// Assume insert and search functions are correct
// Function finds longest word where all prefixes exist
printf("%s", longestWord(words, 6));

medium

A. apple

B. apply

C. appl

D. app

Solution

1. Step 1: Check all prefixes for each word

   Words like "apple" and "apply" have all prefixes present: a, ap, app, appl.

2. Step 2: Compare lengths of valid words

   "apple" and "apply" both have length 5, but "apple" comes first lexicographically.

3. Final Answer:

   apple -> Option A

4. Quick Check:

   Longest valid word = apple [OK]

Hint: Check all prefixes exist, pick longest lex order first [OK]

Common Mistakes:

• Choosing 'apply' ignoring lex order
• Picking shorter words like 'app'
• Not verifying all prefixes exist

4. The following code tries to find the longest word in a dictionary using a Trie but always returns an empty string. What is the bug?

void insert(TrieNode* root, char* word) {
    TrieNode* node = root;
    for (int i = 0; word[i]; i++) {
        int index = word[i] - 'a';
        if (!node->children[index])
            node->children[index] = createNode();
        node = node->children[index];
    }
    node->isEndOfWord = 1;
}

char* longestWord(char** words, int n) {
    TrieNode* root = createNode();
    for (int i = 0; i < n; i++)
        insert(root, words[i]);
    // Missing code to find longest word
    return "";
}

medium

A. The children array size is incorrect

B. The longestWord function does not search the Trie for the longest word

C. The insert function does not mark end of word correctly

D. The root node is not initialized

Solution

1. Step 1: Analyze insert function

   Insert correctly adds words and marks end of word, so no issue here.

2. Step 2: Check longestWord function

   It inserts words but returns empty string without searching Trie for longest word.

3. Final Answer:

   The longestWord function does not search the Trie for the longest word -> Option B

4. Quick Check:

   Missing search logic causes empty output [OK]

Hint: Check if search logic exists after insertion [OK]

Common Mistakes:

• Assuming insert alone finds longest word
• Ignoring missing traversal in longestWord
• Thinking root node is uninitialized

5. You want to find the longest word in a dictionary such that every prefix of the word is also a word in the dictionary. Which approach using a Trie is best to solve this efficiently?

hard

A. Use BFS on Trie without checking end of word flags

B. Sort words by length, then check each word's prefixes in a hash set

C. Insert words into Trie and count total nodes to find longest word

D. Insert all words into Trie, then do DFS checking only nodes marking end of words to build longest word

Solution

1. Step 1: Insert all words into Trie

   Build Trie with all dictionary words, marking end of word nodes.

2. Step 2: Use DFS to find longest word

   Traverse Trie depth-first, only continuing on nodes that mark end of words to ensure all prefixes exist.

3. Step 3: Track longest word during traversal

   Keep updating longest word found by length and lex order during DFS.

4. Final Answer:

   Insert all words into Trie, then do DFS checking only nodes marking end of words to build longest word -> Option D

5. Quick Check:

   Trie + DFS + endOfWord check = longest word [OK]

Hint: Use DFS on Trie nodes with endOfWord true only [OK]

Common Mistakes:

• Ignoring prefix checks during traversal
• Using BFS without endOfWord validation
• Relying on sorting without Trie