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

Concept Flow - Longest Word in Dictionary Using Trie

Start: Insert words into Trie

↓

Build Trie nodes for each char

↓

Mark end of word nodes

↓

DFS from root to find longest word

↓

At each node: Check if word ends here

↓

If yes, continue deeper

↓

Update longest word if current path longer

↓

Return longest word found

Insert all words into a Trie, then use depth-first search to find the longest word where all prefixes are valid words.

Execution Sample

DSA C++

class TrieNode {
public:
  TrieNode* children[26] = {nullptr};
  bool isEnd = false;
};

Defines a Trie node with 26 children pointers and a flag to mark end of a word.

Execution Table

Step	Operation	Nodes in Trie	Pointer Changes	Visual State
1	Insert 'a'	root -> a (isEnd=true)	root->children['a' - 'a'] = new node	root -> a*
2	Insert 'app'	root -> a* -> p -> p (isEnd=true)	a->children['p' - 'a'] = new node, p->children['p' - 'a'] = new node	root -> a* -> p -> p*
3	Insert 'apple'	root -> a* -> p -> p* -> l -> e (isEnd=true)	p->children['l' - 'a'] = new node, l->children['e' - 'a'] = new node	root -> a* -> p -> p* -> l -> e*
4	Insert 'apply'	root -> a* -> p -> p* -> l -> e* and l -> y (isEnd=true)	l->children['y' - 'a'] = new node	root -> a* -> p -> p* -> l -> e*, y*
5	Insert 'banana'	root -> a* ... and b -> a -> n -> a -> n -> a (isEnd=true)	root->children['b' - 'a'] = new node, chain for 'banana'	root -> a* ... b -> a -> n -> a -> n -> a*
6	DFS start at root	All nodes built	Set longestWord = ''	No change
7	Visit 'a' node (isEnd=true)	At node 'a'	longestWord = 'a'	Current longest: 'a'
8	Visit 'p' after 'a' (not end)	At node 'p'	Skip deeper (prefix not word)	No update
9	Visit second 'p' after 'ap' (isEnd=true)	At node 'p'	longestWord = 'app'	Current longest: 'app'
10	Visit 'l' after 'app' (not end)	At node 'l'	Skip deeper	No update
11	Visit 'e' after 'appl' (isEnd=true)	At node 'e'	longestWord = 'apple'	Current longest: 'apple'
12	Visit 'y' after 'appl' (isEnd=true)	At node 'y'	longestWord = 'apply' (tie, lex order decides)	Current longest: 'apple' or 'apply'
13	Visit 'b' node (not end)	At node 'b'	Skip deeper	No update
14	DFS complete	Longest word found	Return 'apple'	Final longest word: 'apple'

💡 DFS ends after visiting all nodes; longest word with all prefixes present is 'apple'

Variable Tracker

Variable	Start	After Step 7	After Step 9	After Step 11	After Step 12	Final
longestWord	''	'a'	'app'	'apple'	'apple'	'apple'
currentNode	root	'a'	'p'	'e'	'y'	null (DFS end)
Trie Size	1 (root)	2	4	7	8	14 nodes total

Key Moments - 3 Insights

Why do we skip deeper when a node is not marked as end of a word during DFS?

Because the problem requires all prefixes to be valid words. If a node is not an end, its prefix is incomplete, so deeper paths can't form valid words. See execution_table rows 8 and 10.

How do we decide between words of the same length like 'apple' and 'apply'?

We choose the lexicographically smaller word. In the example, 'apple' is chosen over 'apply'. See execution_table row 12.

Why do we mark nodes with isEnd=true during insertion?

Marking nodes as end of word helps DFS know which prefixes are valid words, essential for checking the condition. See execution_table rows 1-5.

Visual Quiz - 3 Questions

Look at the execution_table, what is the longestWord after step 9?

A 'apple'

B 'a'

C 'app'

D ''

💡 Hint

Check the 'longestWord' variable in variable_tracker after step 9.

At which step does the DFS skip deeper because the node is not an end of a word?

A Step 8

B Step 11

C Step 7

D Step 14

💡 Hint

Look at execution_table rows where 'Skip deeper' is mentioned in Pointer Changes.

If the word 'app' was not inserted, how would the longestWord after step 11 change?

A 'apple'

B 'a'

C ''

D 'apply'

💡 Hint

Without 'app' marked as end, prefixes for 'apple' fail; see key_moments about prefix checks.

Concept Snapshot

Trie stores words by characters in nodes.
Mark nodes where words end.
Use DFS to find longest word with all prefixes valid.
Skip paths where prefix node is not end.
Choose lex smaller if tie in length.
Return longest valid word found.

Full Transcript

We build a Trie by inserting each word character by character, marking nodes where words end. Then, we perform a depth-first search starting from the root. At each node, we check if it marks the end of a word. If yes, we continue deeper; if not, we skip that path because the problem requires all prefixes to be valid words. We keep track of the longest word found so far, updating it when we find a longer valid word or a lexicographically smaller word of the same length. Finally, we return the longest word found after visiting all nodes.

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 reverse the words in the dictionary

C. To count the total number of words

D. To efficiently store and search words by their prefixes

Solution

1. Step 1: Understand Trie usage

   A Trie stores words by their prefixes, allowing quick prefix checks.

2. Step 2: Relate to longest word search

   Finding the longest word with all prefixes present is easier with prefix-based storage.

3. Final Answer:

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

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie stores prefixes for fast word checks [OK]

Common Mistakes:

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

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

easy

A. class TrieNode { public: vector<TrieNode> children; bool isEnd; TrieNode() { isEnd = false; } };

B. class TrieNode { public: TrieNode* children[26]; bool isEnd; TrieNode() { for(int i=0; i<26; i++) children[i] = nullptr; isEnd = false; } };

C. class TrieNode { public: TrieNode* children[52]; bool isEnd; TrieNode() { for(int i=0; i<52; i++) children[i] = nullptr; isEnd = false; } };

D. class TrieNode { public: int children[26]; bool isEnd; TrieNode() { for(int i=0; i<26; i++) children[i] = 0; isEnd = true; } };

Solution

1. Step 1: Check children type and size

   Children should be pointers to TrieNode, size 26 for lowercase letters.

2. Step 2: Check initialization

   Initialize all children to nullptr and isEnd to false.

3. Final Answer:

   class TrieNode { public: TrieNode* children[26]; bool isEnd; TrieNode() { for(int i=0; i<26; i++) children[i] = nullptr; isEnd = false; } }; -> Option B

4. Quick Check:

   Pointer array size 26, initialized null [OK]

Hint: Use pointer array size 26 for lowercase letters [OK]

Common Mistakes:

• Using int array instead of pointers
• Wrong array size (52 instead of 26)
• Not initializing children to nullptr

3. What will be the output of the following code snippet that inserts words into a Trie and finds the longest word where all prefixes exist? vector<string> words = {"a", "ap", "app", "appl", "apple", "apply"}; // After building Trie and searching longest word cout << longestWord(words) << endl;

medium

A. "apple"

B. "apply"

C. "appl"

D. "app"

Solution

1. Step 1: Insert all words into Trie

   Words "a", "ap", "app", "appl", "apple", "apply" are inserted.

2. Step 2: Find longest word with all prefixes present

   "apple" and "apply" both have all prefixes present, but "apple" comes first lexicographically.

3. Final Answer:

   "apple" -> Option A

4. Quick Check:

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

Hint: Check all prefixes exist; choose longest lex smallest [OK]

Common Mistakes:

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

4. Identify the error in this Trie insertion code snippet for lowercase English letters: void insert(TrieNode* root, string word) { TrieNode* node = root; for (char c : word) { int index = c - 'a'; if (!node->children[index]) node->children[index] = new TrieNode(); node = node->children[index]; } node->isEnd = true; }

medium

A. No error; code is correct

B. Incorrect calculation of index from character

C. Missing initialization of root node before insertion

D. Not marking the end of word after insertion

Solution

1. Step 1: Check index calculation

   Index is correctly calculated as c - 'a' for lowercase letters.

2. Step 2: Verify insertion and end marking

   Children nodes are created if null, and isEnd is set true after insertion.

3. Final Answer:

   No error; code is correct -> Option A

4. Quick Check:

   Insertion logic correct [OK]

Hint: Check index and isEnd marking carefully [OK]

Common Mistakes:

• Miscomputing index for uppercase letters
• Forgetting to mark isEnd true
• Not initializing root before use (outside snippet)

5. Given a list of words, how would you modify the Trie-based approach to find the longest word where every prefix is also a valid word, but now the dictionary may contain uppercase and lowercase letters mixed? Choose the best approach.

hard

A. Ignore case and treat uppercase and lowercase as same during insertion

B. Convert all words to lowercase before inserting into Trie and searching

C. Use a Trie with 52 children per node to handle both cases distinctly

D. Use a hash map instead of Trie for faster prefix checks

Solution

1. Step 1: Understand case sensitivity

   Uppercase and lowercase letters differ; need to distinguish them in Trie.

2. Step 2: Adjust Trie structure

   Use 52 children per node (26 lowercase + 26 uppercase) to store all letters distinctly.

3. Final Answer:

   Use a Trie with 52 children per node to handle both cases distinctly -> Option C

4. Quick Check:

   Handle case by expanding Trie size [OK]

Hint: Expand Trie children to 52 for mixed case [OK]

Common Mistakes:

• Converting all to lowercase loses case info
• Ignoring case causes wrong matches
• Using hash map loses prefix tree benefits