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.