Longest Word in Dictionary Using Trie in DSA Typescript

Mental Model

We build a tree where each path from root to a node forms a word prefix. We find the longest word where every prefix is also a word.

Analogy: Imagine a tree of building blocks where each block is a letter. To build the tallest tower (longest word), every smaller tower below it must also be complete and stable (valid word).

root
 ↓
 a -> p -> p -> l -> e
 ↑    ↑    ↑    ↑    ↑
 w    w    w    w    w

w = word ends here (valid word)

Dry Run Walkthrough

Input: words: ["a", "app", "apple", "apply", "ap", "appl"]

Goal: Find the longest word where all prefixes are also words in the list

Step 1: Insert 'a' into trie, mark end of word at 'a'

root -> a[w]

w = word ends here

Why: We start building the trie with the smallest word

Step 2: Insert 'ap' into trie, mark end of word at 'p'

root -> a[w] -> p[w]

w = word ends here

Why: Add next word and mark its end to track valid prefixes

Step 3: Insert 'app' into trie, mark end of word at second 'p'

root -> a[w] -> p[w] -> p[w]

w = word ends here

Why: Continue building trie with longer word and mark valid prefix

Step 4: Insert 'appl' into trie, mark end of word at 'l'

root -> a[w] -> p[w] -> p[w] -> l[w]

w = word ends here

Why: Add next prefix word to trie

Step 5: Insert 'apple' into trie, mark end of word at 'e'

root -> a[w] -> p[w] -> p[w] -> l[w] -> e[w]

w = word ends here

Why: Add full word to trie

Step 6: Insert 'apply' into trie, mark end of word at 'y'

root -> a[w] -> p[w] -> p[w] -> l[w] -> e[w]
                                   ↓
                                   y[w]

w = word ends here

Why: Add another full word with same prefix

Step 7: Search trie for longest word where all prefixes are words

Check 'a' (valid), 'ap' (valid), 'app' (valid), 'appl' (valid), 'apple' (valid), 'apply' (valid)

Why: We verify each prefix is a word to find longest valid word

Step 8: Choose longest word with all prefixes valid: 'apple' or 'apply'

Longest word found: 'apple' (lexicographically smaller)

Why: Return longest word with all prefixes valid; if tie, choose lex smaller

Result:

root -> a[w] -> p[w] -> p[w] -> l[w] -> e[w]
                                   ↓
                                   y[w]

Longest word: apple

Annotated Code

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isWord: boolean = false;
}

class Trie {
  root: TrieNode = new TrieNode();

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

  longestWord(): string {
    let result = "";

    const dfs = (node: TrieNode, path: string): void => {
      if (node !== this.root && !node.isWord) return; // skip if prefix not a word

      if (path.length > result.length || (path.length === result.length && path < result)) {
        result = path;
      }

      for (const [char, child] of [...node.children.entries()].sort((a, b) => a[0].localeCompare(b[0]))) {
        dfs(child, path + char);
      }
    };

    dfs(this.root, "");
    return result;
  }
}

// Driver code
const words = ["a", "app", "apple", "apply", "ap", "appl"];
const trie = new Trie();
for (const word of words) {
  trie.insert(word);
}
console.log(trie.longestWord());

if (!node.children.has(char)) { node.children.set(char, new TrieNode()); }

Create new node if character path does not exist

node = node.children.get(char)!;

Advance node pointer to child node for next character

node.isWord = true;

Mark current node as end of a valid word

if (node !== this.root && !node.isWord) return;

Stop DFS if current prefix is not a valid word

if (path.length > result.length || (path.length === result.length && path < result)) { result = path; }

Update longest word if current path is longer or lex smaller if tie

for (const [char, child] of [...node.children.entries()].sort((a, b) => a[0].localeCompare(b[0]))) { dfs(child, path + char); }

Traverse children in alphabetical order to ensure lex order

Output

apple

Complexity Analysis

Time: O(N * L) where N is number of words and L is max word length because we insert each character once and DFS visits nodes once

Space: O(N * L) for trie storage as each character creates a node in worst case

vs Alternative: Compared to sorting and checking prefixes in array (O(N log N * L)), trie offers efficient prefix checks and lex order traversal

Edge Cases

Empty list of words

Returns empty string as no words exist

DSA Typescript

if (node !== this.root && !node.isWord) return;

Words with no valid prefix chain (e.g., ['b', 'ba', 'bac'] but 'b' missing)

Skips words where prefix is not a word, returns empty or shorter valid word

DSA Typescript

if (node !== this.root && !node.isWord) return;

Multiple longest words with same length

Returns lexicographically smallest word due to sorted DFS traversal

DSA Typescript

for (const [char, child] of [...node.children.entries()].sort((a, b) => a[0].localeCompare(b[0]))) { dfs(child, path + char); }

When to Use This Pattern

When asked to find the longest word with all prefixes present in a dictionary, use a trie to efficiently check prefixes and traverse lex order.

Common Mistakes

Mistake: Not checking if all prefixes are valid words before extending path
Fix: Add condition to stop DFS if current node is not marked as a word

Mistake: Not sorting children before DFS causing wrong lexicographical order
Fix: Sort children keys before DFS traversal to ensure lex order

Summary

Builds a trie from words and finds the longest word where every prefix is also a word.

Use when you need to find words with valid prefix chains efficiently.

The key is to stop exploring paths where prefixes are not words and traverse children in lex order.

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