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

Concept Flow - Longest Word in Dictionary Using Trie

Build Trie from words

↓

Insert each word letter by letter

↓

Mark end of word nodes

↓

Start DFS from root

↓

For each child node

↓

Check if node is end of a word

↓

Update longest word if longer

↓

Return longest word found

Build a trie from the dictionary words, then use depth-first search to find the longest word where all prefixes are present.

Execution Sample

DSA Go

words := []string{"a", "app", "apple", "apply", "ap"}
trie := NewTrie()
for _, w := range words {
    trie.Insert(w)
}
longest := trie.LongestWord()

Insert words into trie and find the longest word with all prefixes present.

Execution Table

Step	Operation	Nodes in Trie	Pointer Changes	Visual State
1	Insert 'a'	root -> a(end)	root.children['a'] created	root -> a(end) a(end)
2	Insert 'app'	root -> a(end) -> p -> p(end)	a.children['p'] created, p.children['p'] created, last p marked end	root -> a(end) a(end) -> p p -> p(end)
3	Insert 'apple'	root -> a(end) -> p -> p(end) -> l -> e(end)	p.children['l'] created, l.children['e'] created, e marked end	root -> a(end) a(end) -> p p -> p(end) -> l l -> e(end)
4	Insert 'apply'	root -> a(end) -> p -> p(end) -> l -> e(end), y(end)	l.children['y'] created, y marked end	root -> a(end) a(end) -> p p -> p(end) -> l l -> e(end), y(end)
5	Insert 'ap'	root -> a(end) -> p(end) -> p(end) -> l -> e(end), y(end)	a.children['p'] marked end	root -> a(end) a(end) -> p(end) p -> p(end) -> l l -> e(end), y(end)
6	Start DFS from root	No change	current = root	root
7	DFS to 'a' node (end=true)	No change	current = a	root -> a(end)
8	DFS to 'p' node (end=true)	No change	current = p	root -> a(end) -> p(end)
9	DFS to next 'p' node (end=true)	No change	current = p	root -> a(end) -> p(end) -> p(end)
10	DFS to 'l' node (end=false)	Skip this branch	No pointer change	Skip l branch since end=false
11	DFS to 'l' node (end=false) skipped, backtrack	No change	Back to p node	root -> a(end) -> p(end) -> p(end)
12	Update longest word to 'app'	No change	longest = 'app'	Longest word: 'app'
13	DFS to 'p' node (end=true) backtrack to 'a'	No change	Back to a node	root -> a(end)
14	DFS to 'p' node (end=true) backtrack to root	No change	Back to root	root
15	Return longest word 'app'	No change	Done	Longest word: 'app'

💡 DFS ends after exploring all nodes with end=true; longest word found is 'app'

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 12	Final
longest	""	""	""	""	""	""	"app"	"app"
current_node	root	a	p	p	p	p	p	root
Trie Size (nodes)	1	2	4	7	9	9	9	9

Key Moments - 3 Insights

Why do we skip DFS branches where the node is not marked as end of a word?

Because the problem requires all prefixes of the word to be present. If a node is not an end of a word, that prefix is missing. See execution_table step 10 where the 'l' node is skipped.

Why do we mark nodes as end of word during insertion?

Marking nodes as end of word helps us know which prefixes are valid words. This is crucial during DFS to decide if we can continue exploring deeper. Refer to execution_table steps 1-5.

Why does the longest word update only at nodes marked as end of word?

Because only words with all prefixes present count. We update longest word when we reach a node that marks a complete word. See step 12 where longest word updates to 'app'.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what change happens to the node 'p' after inserting 'ap'?

A The 'p' node is marked as end of a word

B A new child node is created under 'p'

C The root node is marked as end

D No change happens

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 5 in execution_table

At which step does the longest word get updated to 'app'?

A Step 8

B Step 10

C Step 12

D Step 15

💡 Hint

Look at the 'Operation' and 'Visual State' columns in execution_table for longest word updates

If the word 'apple' was missing from the input, how would the trie size after step 4 change?

A It would be smaller because 'l' and 'e' nodes wouldn't be created

B It would be larger because more nodes are needed

C It would be the same size

D The trie would be empty

💡 Hint

Check variable_tracker for 'Trie Size (nodes)' after step 4 and consider nodes created for 'apple'

Concept Snapshot

Longest Word in Dictionary Using Trie
- Build trie by inserting words letter by letter
- Mark nodes where words end
- Use DFS to explore nodes only if they mark end of a word
- Track longest word during DFS
- Return longest word with all prefixes present

Full Transcript

We build a trie by inserting each word letter by letter, marking nodes where words end. Then we use depth-first search starting from the root. We only continue DFS on nodes that mark the end of a word, ensuring all prefixes exist. During DFS, we update the longest word found. Finally, we return the longest word where all prefixes are present. This method efficiently finds the longest valid word in the dictionary.

Practice

1. What is the main purpose of using a Trie data structure when finding the longest word in a dictionary?

easy

A. To reverse the words quickly

B. To sort words alphabetically

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 breaking them into characters and linking nodes for prefixes.

2. Step 2: Connect Trie to longest word search

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

3. Final Answer:

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

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 Go code snippets correctly initializes a Trie node struct for storing children nodes?

easy

A. type TrieNode struct { children map[int]string; isWord string }

B. type TrieNode struct { children []int; isWord int }

C. type TrieNode struct { children map[rune]*TrieNode; isWord bool }

D. type TrieNode struct { children []string; isWord bool }

Solution

1. Step 1: Identify correct children type

   Children should map characters (rune) to TrieNode pointers for branching.

2. Step 2: Check isWord type

   isWord is a boolean indicating if node ends a valid word.

3. Final Answer:

   type TrieNode struct { children map[rune]*TrieNode; isWord bool } -> Option C

4. Quick Check:

   Children map[rune]*TrieNode and bool isWord [OK]

Hint: Children map uses rune keys and TrieNode pointers [OK]

Common Mistakes:

• Using slices instead of maps for children
• Wrong data types for children or isWord
• Using int or string instead of rune keys

3. Given the following Go code snippet that inserts words into a Trie and finds the longest word, what will be printed?

words := []string{"a", "app", "apple", "apply", "ap"}
trie := NewTrie()
for _, w := range words {
    trie.Insert(w)
}
result := trie.LongestWord()
fmt.Println(result)

medium

A. "app"

B. "apply"

C. "a"

D. "apple"

Solution

1. Step 1: Insert words into Trie

   All words "a", "ap", "app", "apple", "apply" are inserted.

2. Step 2: Find longest word built from prefixes

   "app" has all prefixes "a", "ap", "app" present as words. "apple" and "apply" lack "appl" prefix.

3. Final Answer:

   "app" -> Option A

4. Quick Check:

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

Hint: Longest word with all prefixes present wins, lex order breaks ties [OK]

Common Mistakes:

• Choosing "apple" or "apply" ignoring missing "appl"
• Picking lexicographically later word
• Not inserting all words before search

4. In the following Go code for inserting words into a Trie, what is the bug that prevents correct longest word detection?

func (t *Trie) Insert(word string) {
    node := t.root
    for _, ch := range word {
        if node.children[ch] == nil {
            node.children[ch] = &TrieNode{}
        }
        node = node.children[ch]
    }
    node.isWord = false
}

medium

A. isWord should be set to true, not false

B. children map is not initialized

C. Loop variable ch should be int, not rune

D. Function should return a value

Solution

1. Step 1: Check isWord assignment

   isWord marks end of a valid word and must be true, not false.

2. Step 2: Understand impact on longest word search

   Setting isWord false means no word end is recognized, breaking longest word logic.

3. Final Answer:

   isWord should be set to true, not false -> Option A

4. Quick Check:

   isWord = true marks word end [OK]

Hint: Set isWord true at word end to mark valid words [OK]

Common Mistakes:

• Setting isWord false instead of true
• Not initializing children map before use
• Ignoring rune type for characters

5. You have a list of words: ["w", "wo", "wor", "worl", "world", "banana", "ban", "bana", "banan"]. Using a Trie, which word will be the longest word in the dictionary where every prefix is also a word? Assume ties are broken by lexicographical order.

hard

A. "worl"

B. "world"

C. "banana"

D. "banan"

Solution

1. Step 1: Check prefixes for each candidate

   "world" has prefixes "w", "wo", "wor", "worl" all present.

2. Step 2: Check "banana" and its prefixes

   "banana" lacks prefixes like "b", "ba", so it fails.

3. Step 3: Compare longest valid words

   "world" (length 5) is longest with all prefixes present; "banana" (6) invalid, "banan" also invalid.

4. Final Answer:

   "world" -> Option B

5. Quick Check:

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

Hint: Check all prefixes exist; longest with lex order wins [OK]

Common Mistakes:

• Ignoring missing prefixes for banana
• Choosing shorter words
• Not applying lexicographical tie-break