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

↓

Build candidate words by adding letters

↓

Keep track of longest valid word

↓

Return longest word found

Build a Trie from all words, then traverse it to find the longest word where every prefix is also a word.

Execution Sample

DSA Javascript

class TrieNode {
  constructor() {
    this.children = {};
    this.isWord = false;
  }
}
// Insert words and find longest word

This code builds a Trie node class and inserts words to find the longest valid word.

Execution Table

Step	Operation	Nodes in Trie	Pointer Changes	Visual State
1	Insert 'a'	root -> a(isWord: true)	root.children['a'] created	root └─ a*
2	Insert 'app'	root -> a(isWord: true) -> p -> p(isWord: true)	a.children['p'] created, p.children['p'] created, mark last p isWord true	root └─ a* └─ p └─ p*
3	Insert 'ap'	root -> a(isWord: true) -> p(isWord: true) -> p(isWord: true)	a.children['p'] isWord set true	root └─ a* └─ p* └─ p*
4	Insert 'apple'	root -> a* -> p* -> p* -> l -> e(isWord: true)	p.children['l'] created, l.children['e'] created, mark e isWord true	root └─ a* └─ p* └─ p* └─ l └─ e*
5	Insert 'apply'	root -> a* -> p* -> p* -> l -> e* and y(isWord: true)	l.children['y'] created, mark y isWord true	root └─ a* └─ p* └─ p* └─ l ├─ e* └─ y*
6	Traverse Trie to find longest word	Starting at root	Traverse nodes where isWord true	Current longest: ''
7	Visit 'a' node (isWord: true)	At node 'a'	Add 'a' to current word	Current longest: 'a'
8	Visit 'p' node (isWord: true)	At node 'p' after 'a'	Add 'p' to current word	Current longest: 'ap'
9	Visit next 'p' node (isWord: true)	At node 'p' after 'ap'	Add 'p' to current word	Current longest: 'app'
10	Visit 'l' node (isWord: false)	At node 'l' after 'app'	Cannot continue, 'l' is not end of word	Current longest: 'app'
11	Visit 'e' node (isWord: true) under 'l'	At node 'e' after 'appl'	Add 'e' to current word	Current longest: 'apple'
12	Visit 'y' node (isWord: true) under 'l'	At node 'y' after 'appl'	Add 'y' to current word	Current longest: 'apple' (tie with 'apply', apple chosen lex order)
13	Traversal complete	All nodes visited	Longest word found: 'apple'	Final longest word: 'apple'

💡 Traversal ends after visiting all nodes with isWord true; longest word is 'apple'

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	After Step 11	After Step 12	Final
Trie Size	0	1	3	4	6	7	7	7	7	7	7	7	7	7
Current Word	''	''	''	''	''	''	''	'a'	'ap'	'app'	'app'	'apple'	'apply'	'apple'
Longest Word	''	'a'	'ap'	'app'	'app'	'app'	'app'	'a'	'ap'	'app'	'app'	'apple'	'apple'	'apple'

Key Moments - 3 Insights

Why do we only continue traversal at nodes where isWord is true?

Because the problem requires every prefix of the word to be a valid word. If a node is not marked isWord, it means the prefix up to that node is not a word, so we stop. See execution_table rows 10 and 11.

Why do we mark nodes as isWord true during insertion?

Marking nodes as isWord true shows that the path from root to that node forms a valid word. This helps during traversal to check if prefixes are valid. See execution_table rows 1 to 5.

How do we decide between words of the same length?

We choose the lexicographically smallest word when lengths tie. For example, between 'apple' and 'apply', 'apple' is chosen. See execution_table row 12.

Visual Quiz - 3 Questions

Look at the execution_table at step 9, what is the current longest word?

A 'apple'

B 'ap'

C 'app'

D 'a'

💡 Hint

Check the 'Current longest' column at step 9 in execution_table.

At which step does the traversal stop continuing down a path because the node is not a word end?

A Step 10

B Step 7

C Step 12

D Step 5

💡 Hint

Look for the step where 'Cannot continue' is noted in execution_table.

If the word 'app' was not marked as isWord true during insertion, how would the longest word change?

A 'apple' would still be found

B 'apple' would not be found

C No longest word would be found

D 'app' would be the longest word

💡 Hint

Refer to key_moments about why traversal only continues at nodes marked isWord true.

Concept Snapshot

Longest Word in Dictionary Using Trie:
- Build Trie by inserting words letter by letter
- Mark nodes where words end (isWord = true)
- Traverse Trie only through nodes marked isWord
- Track longest word where all prefixes are valid words
- If tie, choose lexicographically smallest
- Return longest valid word found

Full Transcript

We build a Trie by inserting each word letter by letter, marking nodes where words end. Then, we traverse the Trie from the root, only moving through nodes that mark the end of a word. This ensures every prefix of the word is valid. We keep track of the longest such word found during traversal. If multiple words tie in length, we pick the lexicographically smallest. The traversal stops when no further nodes are valid word ends. Finally, we return the longest word found.

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

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, which helps 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 all about prefixes and fast word lookup [OK]

Common Mistakes:

• Confusing Trie with sorting algorithms
• 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 JavaScript?

easy

A. node[word[i]] = new TrieNode() if not exists

B. node[word[i]] = word[i]

C. node.push(word[i])

D. node[word] = true

Solution

1. Step 1: Understand Trie node insertion

   Each character of the word is a key in the node object; if missing, create a new TrieNode.

2. Step 2: Identify correct syntax

   Using node[word[i]] = new TrieNode() creates a child node for that character if it doesn't exist.

3. Final Answer:

   node[word[i]] = new TrieNode() if not exists -> Option A

4. Quick Check:

   Insert char as child node [OK]

Hint: Insert chars as keys with new nodes if missing [OK]

Common Mistakes:

• Assigning character directly instead of node
• Using array push on object
• Setting whole word as key instead of chars

3. Given the words ["a", "app", "apple", "apply", "ap"], what is the longest word that can be built one character at a time using the Trie method?

medium

A. "apple"

B. "apply"

C. "app"

D. "ap"

Solution

1. Step 1: Check each word buildability

   Words must be built one char at a time with all prefixes present. "a", "ap", "app" are present, but "apple" and "apply" require "appl" which is missing.

2. Step 2: Identify longest valid word

   "app" is the longest word where all prefixes ("a", "ap", "app") exist in the list.

3. Final Answer:

   "app" -> Option C

4. Quick Check:

   Longest buildable word = "app" [OK]

Hint: Check all prefixes exist for each candidate word [OK]

Common Mistakes:

• Assuming "apple" or "apply" are valid without "appl" prefix
• Ignoring prefix existence
• Choosing shortest word instead of longest

4. What is the bug in this Trie insertion snippet for finding the longest word?

for (let char of word) {
  if (!node[char]) {
    node[char] = {};
  }
  node = node[char];
}
node.isWord = true;

medium

A. No bug, code is correct

B. Missing initialization of root node

C. Not marking the end of word properly

D. Using plain object instead of TrieNode class

Solution

1. Step 1: Analyze insertion logic

   The loop creates child nodes if missing and moves down the Trie correctly.

2. Step 2: Check end of word marking

   Setting node.isWord = true marks the end of the word properly.

3. Final Answer:

   No bug, code is correct -> Option A

4. Quick Check:

   Insertion and marking done correctly [OK]

Hint: Mark end of word after insertion loop [OK]

Common Mistakes:

• Forgetting to mark end of word
• Overcomplicating node creation
• Assuming class needed when object works

5. You have a list of words: ["w", "wo", "wor", "worl", "world", "banana", "ban", "bana", "banan"]. Using a Trie, which word is the longest that can be built one character at a time from other words in the list?

hard

A. "banan"

B. "world"

C. "banana"

D. "worl"

Solution

1. Step 1: Verify prefix existence for each candidate

   For "world": prefixes "w", "wo", "wor", "worl", "world" all exist. For "banana": prefixes "b", "ba", "ban", "bana", "banan", "banana" -- but "b" and "ba" are missing. Similarly, "banan" misses "b" and "ba".

2. Step 2: Compare longest buildable words

   "world" is the longest word where all prefixes from length 1 to full length exist in the list.

3. Final Answer:

   "world" -> Option B

4. Quick Check:

   Longest buildable word = "world" [OK]

Hint: Check all prefixes exist before choosing longest word [OK]

Common Mistakes:

• Choosing "banana" without all prefixes
• Ignoring missing prefixes
• Confusing partial prefixes as complete