Longest Word in Dictionary Using Trie in DSA Typescript - 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 node is end of 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 Typescript

const longestWord = (words: string[]): string => {
  class TrieNode {
    children = new Map<string, TrieNode>();
    isWord = false;
  }
  const root = new TrieNode();
  for (const word of words) {
    let curr = root;
    for (const c of word) {
      if (!curr.children.has(c)) {
        curr.children.set(c, new TrieNode());
      }
      curr = curr.children.get(c)!;
    }
    curr.isWord = true;
  }
  let ans = "";
  const dfs = (node: TrieNode, word: string): void => {
    if (!node.isWord) return;
    if (word.length > ans.length || (word.length === ans.length && word < ans)) {
      ans = word;
    }
    for (const [ch, child] of node.children) {
      dfs(child, word + ch);
    }
  };
  root.isWord = true;
  dfs(root, "");
  return ans;
};

This code builds a Trie and finds the longest word with all prefixes present.

Execution Table

Step	Operation	Nodes in Trie	Pointer Changes	Visual State
1	Insert 'a'	Root -> a(isWord=true)	Current = root; Insert 'a'; Mark node 'a' isWord=true	root └─ a*
2	Insert 'app'	Root -> a(isWord=true) -> p -> p(isWord=true)	Traverse root->a; Insert 'p'; Insert 'p'; Mark last 'p' isWord=true	root └─ a* └─ p └─ p*
3	Insert 'apple'	Root -> a* -> p -> p* -> l -> e(isWord=true)	Traverse to last 'p'; Insert 'l'; Insert 'e'; Mark 'e' isWord=true	root └─ a* └─ p └─ p* └─ l └─ e*
4	Insert 'apply'	Root -> a* -> p -> p* -> l -> e* and y(isWord=true)	Traverse to 'l'; Insert 'y'; Mark 'y' isWord=true	root └─ a* └─ p └─ p* └─ l ├─ e* └─ y*
5	Insert 'banana'	Root -> a* -> p -> p* -> l -> e*, y* and b -> a -> n -> a -> n -> a(isWord=true)	Insert 'b' at root; Insert 'a', 'n', 'a', 'n', 'a'; Mark last 'a' isWord=true	root ├─ a* │ └─ p │ └─ p* │ └─ l │ ├─ e* │ └─ y* └─ b └─ a └─ n └─ a └─ n └─ a*
6	DFS Traverse to find longest word	Trie fully built	Start at root; traverse nodes where isWord=true	Longest word updated to 'apple' then 'apply' then 'banana'
7	Return longest word	Longest word = 'banana'	Traversal complete	Result: 'banana'

💡 All words inserted and traversal finished; longest word with all prefixes found.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
Trie Root	empty	a node added	p nodes added	l and e nodes added	y node added	b and banana nodes added	traversal started	traversal finished
Longest Word	""	"a"	"app"	"apple"	"apply"	"banana"	"banana"	"banana"
Current Node	root	node 'a'	node last 'p'	node 'e'	node 'y'	node last 'a' in banana	root during DFS	N/A

Key Moments - 3 Insights

Why do we mark nodes as isWord=true?

Marking nodes as isWord=true shows that the path to this node forms a valid word. This is crucial during DFS (see Step 6) to only continue traversal along valid prefixes.

Why do we only continue DFS on nodes where isWord=true?

Because the problem requires all prefixes to be valid words. If a node is not marked isWord=true, it means the prefix is incomplete, so we stop exploring that path (see Step 6).

How does the longest word get updated during traversal?

At each node marked isWord=true, we check if the current word is longer than the stored longest word. If yes, we update it (see Step 6 and Step 7).

Visual Quiz - 3 Questions

Look at the execution table at Step 4, which new node is marked as a word ending?

A 'y'

B 'l'

C 'e'

D 'p'

💡 Hint

Check the Visual State column at Step 4 where 'y' node is marked with * indicating isWord=true.

At which step does the longest word first become 'banana'?

A Step 5

B Step 6

C Step 7

D Step 4

💡 Hint

Look at Step 6 where DFS traversal updates longest word to 'banana'.

If the word 'ban' was inserted and marked as isWord=true, how would the traversal change?

A Traversal would stop earlier at 'ban' node

B Longest word would become 'ban'

C Traversal would continue deeper into 'banana' nodes

D No change in traversal

💡 Hint

Refer to key moment about continuing DFS only on nodes with isWord=true; adding 'ban' as word allows deeper traversal.

Concept Snapshot

Build a Trie by inserting words letter by letter.
Mark nodes where words end (isWord=true).
Traverse Trie depth-first only along nodes marked isWord=true.
Update longest word when a longer valid word is found.
Return the longest word after traversal.

Full Transcript

We build a Trie from the given dictionary words by inserting each letter as a node. Each node that ends a word is marked with isWord=true. After building, we traverse the Trie depth-first, only moving along nodes where isWord=true to ensure all prefixes are valid words. During traversal, we keep track of the longest word found. Finally, we return this longest word. This method efficiently finds the longest word in the dictionary where every prefix is also a valid 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 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 A

4. Quick Check:

   Trie = prefix search [OK]

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

Common Mistakes:

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

2. Which of the following TypeScript code snippets correctly initializes a Trie node with children and an end-of-word flag?

easy

A. class TrieNode { children: Map = new Map(); isEnd: boolean = false; }

B. class TrieNode { children: string[] = []; isEnd: number = 0; }

C. class TrieNode { children: object = {}; isEnd: string = 'false'; }

D. class TrieNode { children: Map = new Map(); isEnd: boolean = true; }

Solution

1. Step 1: Check children type

   Children should map characters (string) to TrieNode objects, so Map is correct.

2. Step 2: Check isEnd flag type

   isEnd should be boolean to mark word end, so boolean = false is correct.

3. Final Answer:

   class TrieNode { children: Map = new Map(); isEnd: boolean = false; } -> Option A

4. Quick Check:

   Correct types = class TrieNode { children: Map = new Map(); isEnd: boolean = false; } [OK]

Hint: Use Map and boolean for TrieNode [OK]

Common Mistakes:

• Using array instead of Map for children
• Using wrong types for isEnd flag
• Mixing key and value types in Map

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

const words = ["a", "app", "apple", "apply", "ap"];
const trie = new Trie();
words.forEach(word => trie.insert(word));
console.log(trie.findLongestWord());

medium

A. "a"

B. "apply"

C. "apple"

D. "app"

Solution

1. Step 1: Insert words into Trie

   Words "a", "app", "apple", "apply", "ap" are inserted. Trie stores prefixes for all.

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

   "app" has all prefixes present: "a", "ap", "app". "apple" and "apply" require "appl" which is not a word in the list.

3. Final Answer:

   "app" -> Option D

4. Quick Check:

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

Hint: Choose longest word with all prefixes present, lex smallest if tie [OK]

Common Mistakes:

• Choosing "apple" or "apply" without checking if "appl" is a word
• Ignoring that intermediate prefixes like "appl" must be full words
• Picking the overall longest word without prefix validation

4. Consider this buggy TypeScript code snippet for inserting words into a Trie:

insert(word: string) {
  let node = this.root;
  for (const char of word) {
    node = node.children.get(char);
    if (!node.children.has(char)) {
      node.children.set(char, new TrieNode());
    }
  }
  node.isEnd = true;
}

What is the main issue causing a runtime error?

medium

A. The loop does not iterate over all characters

B. The isEnd flag is set before inserting nodes

C. node.children.get(char) can return undefined, causing node to be undefined

D. The children map is not initialized

Solution

1. Step 1: Analyze node update inside loop

   node.children.get(char) may return undefined if key missing, but code assumes it returns TrieNode.

2. Step 2: Identify cause of runtime error

   If undefined assigned to node, next iteration fails accessing children of undefined.

3. Final Answer:

   node.children.get(char) can return undefined, causing node to be undefined -> Option C

4. Quick Check:

   Undefined node from get() causes error [OK]

Hint: Check if get() can return undefined before assignment [OK]

Common Mistakes:

• Ignoring possibility of undefined from Map.get()
• Assuming loop skips characters
• Confusing isEnd flag placement

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 in the list?

hard

A. "banana"

B. "world"

C. "banan"

D. "worl"

Solution

1. Step 1: Check prefixes for "world"

   Prefixes: "w", "wo", "wor", "worl" all exist in list.

2. Step 2: Check prefixes for "banana" and "banan"

   "banana" and "banan" are missing shorter prefixes like "b" and "ba" which are not in the list.

3. Step 3: Compare valid longest words

   "world" is longest with all prefixes present; others longer but invalid.

4. Final Answer:

   "world" -> Option B

5. Quick Check:

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

Hint: Check all prefixes exist; longest valid word wins [OK]

Common Mistakes:

• Choosing "banana" ignoring missing prefix like "b"
• Confusing similar prefixes
• Not verifying all prefixes exist