Longest Word in Dictionary Using Trie in DSA Java - 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

↓

Traverse Trie DFS

↓

Check if prefix is valid word

↓

Update longest word if longer

↓

Return longest word found

Build a Trie from the dictionary words, then traverse it depth-first to find the longest word where all prefixes are valid words.

Execution Sample

DSA Java

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

// Insert words and find longest word with all prefixes

This code builds a Trie from words and finds the longest word where every prefix is also a word.

Execution Table

Step	Operation	Nodes in Trie	Pointer Changes	Visual State
1	Insert 'a'	Root -> a (isWord=false)	root.children['a' - 'a'] = new TrieNode	root -> a
2	Mark 'a' end	Root -> a (isWord=true)	a.isWord = true	root -> a*
3	Insert 'app'	root -> a* -> p -> p	a.children['p' - 'a'] = new TrieNode, p.children['p' - 'a'] = new TrieNode	root -> a* -> p -> p
4	Mark 'app' end	root -> a* -> p -> p (isWord=true)	last p.isWord = true	root -> a* -> p -> p*
5	Insert 'apple'	root -> a* -> p -> p* -> l -> e	p.children['l' - 'a'] = new TrieNode, l.children['e' - 'a'] = new TrieNode	root -> a* -> p -> p* -> l -> e
6	Mark 'apple' end	root -> a* -> p -> p* -> l -> e (isWord=true)	e.isWord = true	root -> a* -> p -> p* -> l -> e*
7	Insert 'apply'	root -> a* -> p -> p* -> l -> e* and y	l.children['y' - 'a'] = new TrieNode	root -> a* -> p -> p* -> l -> e* and y
8	Mark 'apply' end	root -> a* -> p -> p* -> l -> y (isWord=true)	y.isWord = true	root -> a* -> p -> p* -> l -> y*
9	Insert 'banana'	root -> b -> a -> n -> a -> n -> a	root.children['b' - 'a'] = new TrieNode, chain created	root -> b -> a -> n -> a -> n -> a
10	Mark 'banana' end	root -> b -> a -> n -> a -> n -> a (isWord=true)	last a.isWord = true	root -> b -> a -> n -> a -> n -> a*
11	DFS Traverse Trie	Check nodes with isWord true	Traverse children if prefix valid	Track longest word
12	Longest word found: 'a'	Longest word = 'a'	Return longest word	Result: a

💡 All words inserted and Trie fully traversed; longest word with all prefixes found.

Variable Tracker

Variable	Start	After Step 2	After Step 6	After Step 10	Final
root.children['a']	null	TrieNode (isWord=true)	TrieNode (with p chain)	TrieNode (with p chain)	TrieNode (with p chain)
root.children['b']	null	null	null	TrieNode (banana chain)	TrieNode (banana chain)
longestWord	""	"a"	"a"	"a"	"a"

Key Moments - 3 Insights

Why do we mark isWord=true at the last node of each inserted word?

Marking isWord=true (see steps 2,4,6,8,10) tells us this node ends a valid word, which is essential to check prefixes during traversal.

Why do we only continue DFS traversal if the current node's isWord is true?

Because the problem requires all prefixes to be valid words, we stop exploring branches where isWord is false (see step 11), ensuring only valid prefix chains.

How does the Trie structure help find the longest word efficiently?

Trie stores shared prefixes once, so traversal checks prefixes quickly without repeated string operations (see steps 11-12).

Visual Quiz - 3 Questions

Look at the execution table at step 6, what is the visual state of the Trie?

A root -> a* -> p -> p* -> l -> e*

B root -> a -> p -> p -> l -> e

C root -> b -> a -> n -> a -> n -> a*

D root -> a* -> p* -> l -> e

💡 Hint

Check the 'Visual State' column at step 6 in the execution_table.

At which step does the Trie first contain the word 'banana'?

A Step 7

B Step 10

C Step 9

D Step 11

💡 Hint

Look at the 'Operation' and 'Nodes in Trie' columns for when 'banana' nodes are created.

If we did not mark isWord=true at step 4, how would the longest word change?

A Longest word would be 'a'

B Longest word would still be 'a'

C Longest word would be 'app'

D No longest word would be found

💡 Hint

Refer to key_moments about prefix validation and isWord marking.

Concept Snapshot

Longest Word in Dictionary Using Trie
- Build Trie by inserting words letter by letter
- Mark end of word nodes with isWord=true
- Traverse Trie depth-first checking isWord to ensure prefixes
- Update longest word when all prefixes valid
- Return longest word found
- Efficient prefix checks via Trie structure

Full Transcript

We build a Trie by inserting each word letter by letter, marking nodes where words end. Then we traverse the Trie depth-first, only continuing down paths where nodes mark valid words. This ensures all prefixes of a candidate word are valid. We track the longest such word during traversal. The Trie structure helps by sharing prefixes and allowing quick checks. The final result is 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 efficiently store and search words by their prefixes

B. To sort words alphabetically

C. To count the total number of words

D. To reverse the words quickly

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 Trie prefix checks.

3. Final Answer:

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

4. Quick Check:

   Trie = prefix search [OK]

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

Common Mistakes:

• Confusing Trie with sorting structures
• Thinking Trie reverses words
• Assuming Trie counts words only

2. Which of the following is the correct way to insert a word into a Trie node in Java?

easy

A. node.children[word[i] - 'a'] = new TrieNode();

B. node.children[word.charAt(i) - 'a'] = new TrieNode();

C. node.children[word.charAt(i)] = new TrieNode();

D. node.children[word.charAt(i) + 'a'] = new TrieNode();

Solution

1. Step 1: Understand character indexing

   Characters are converted to index by subtracting 'a' to map 'a' to 0, 'b' to 1, etc.

2. Step 2: Check Java syntax for charAt

   Java uses word.charAt(i) to get character at index i.

3. Final Answer:

   node.children[word.charAt(i) - 'a'] = new TrieNode(); -> Option B

4. Quick Check:

   Correct char indexing = node.children[word.charAt(i) - 'a'] = new TrieNode(); [OK]

Hint: Use charAt(i) - 'a' for array index in Java [OK]

Common Mistakes:

• Using word[i] instead of charAt(i)
• Adding 'a' instead of subtracting
• Using char directly without index conversion

3. What will be the output of the following Java code snippet that uses a Trie to find the longest word?

String[] words = {"a", "app", "ap", "apply", "apple"};
LongestWordInDictionaryUsingTrie trie = new LongestWordInDictionaryUsingTrie();
System.out.println(trie.longestWord(words));

medium

A. "app"

B. "apply"

C. "apple"

D. "ap"

Solution

1. Step 1: Insert all words into Trie

   Words inserted: "a", "app", "ap", "apply", "apple".

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

   "app" is longest where all prefixes "a", "ap", "app" exist. "apple" and "apply" prefixes "appl" missing.

3. Final Answer:

   "app" -> Option A

4. Quick Check:

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

Hint: Longest word must have all prefixes present [OK]

Common Mistakes:

• Choosing longest word ignoring prefix condition
• Confusing "apple" and "apply" as valid
• Ignoring shorter prefix words

4. Identify the error in this Java method snippet for searching the longest word in a Trie:

public String longestWord(String[] words) {
  TrieNode root = new TrieNode();
  for (String w : words) insert(root, w);
  String result = "";
  dfs(root, new StringBuilder(), result);
  return result;
}

private void dfs(TrieNode node, StringBuilder path, String result) {
  if (node == null) return;
  if (!node.isWord && path.length() != 0) return;
  if (path.length() > result.length()) result = path.toString();
  for (int i = 0; i < 26; i++) {
    if (node.children[i] != null) {
      path.append((char)(i + 'a'));
      dfs(node.children[i], path, result);
      path.deleteCharAt(path.length() - 1);
    }
  }
}

medium

A. The insert method is missing

B. The dfs method does not check for null children

C. The result string is not updated correctly inside dfs due to pass-by-value

D. The path StringBuilder is not cleared after recursion

Solution

1. Step 1: Analyze result parameter usage

   String is immutable and passed by value, so updating result inside dfs does not affect outer variable.

2. Step 2: Understand effect on final output

   Result remains empty because changes inside dfs do not persist outside recursion.

3. Final Answer:

   The result string is not updated correctly inside dfs due to pass-by-value -> Option C

4. Quick Check:

   String immutability causes result update failure [OK]

Hint: Use a mutable object or class field for result [OK]

Common Mistakes:

• Assuming String updates persist in recursion
• Ignoring missing insert method
• Overlooking null checks in children

5. Given a list of words, how would you modify the Trie-based algorithm to return the lexicographically smallest longest word when multiple longest words exist?

hard

A. Store all words in a list and pick the smallest after Trie traversal

B. Sort the input words first and insert into Trie in reverse order

C. Use a max heap to store all longest words and pop the smallest lexicographically

D. Traverse children in alphabetical order during DFS and update result only if new word is longer or lex smaller

Solution

1. Step 1: Traverse children in alphabetical order

   DFS visits children from 'a' to 'z' ensuring lex order traversal.

2. Step 2: Update result conditionally

   Update result only if new word is longer or same length but lex smaller.

3. Step 3: Ensure final result is lex smallest longest word

   This approach naturally picks lex smallest among longest words.

4. Final Answer:

   Traverse children in alphabetical order during DFS and update result only if new word is longer or lex smaller -> Option D

5. Quick Check:

   Lex order DFS + conditional update = Traverse children in alphabetical order during DFS and update result only if new word is longer or lex smaller [OK]

Hint: DFS children from 'a' to 'z' and update result carefully [OK]

Common Mistakes:

• Sorting input but not controlling DFS order
• Using data structures that add unnecessary complexity
• Ignoring lex order during traversal