Longest Word in Dictionary Using Trie in DSA Javascript

Mental Model

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

Analogy: Imagine a family tree where each generation adds a letter. We want the longest name where every smaller name before it is also in the family.

root
 ↓
 t -> r -> i -> e
 ↑
 start

Dry Run Walkthrough

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

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

Step 1: Insert 'a' into the trie

root -> a* (end of word)
 ↑

Why: We add the first word and mark its end

Step 2: Insert 'ap' into the trie

root -> a* -> p* (end of word)
 ↑

Why: Add second word, mark end at 'p'

Step 3: Insert 'app' into the trie

root -> a* -> p* -> p* (end of word)
 ↑

Why: Add third word, mark end at second 'p'

Step 4: Insert 'appl' into the trie

root -> a* -> p* -> p* -> l* (end of word)
 ↑

Why: Add fourth word, mark end at 'l'

Step 5: Insert 'apple' into the trie

root -> a* -> p* -> p* -> l* -> e* (end of word)
 ↑

Why: Add fifth word, mark end at 'e'

Step 6: Insert 'apply' into the trie

root -> a* -> p* -> p* -> l* -> y* (end of word)
 ↑

Why: Add sixth word, mark end at 'y'

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

Check 'a', 'ap', 'app', 'appl', 'apple', 'apply' prefixes

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

Step 8: Choose 'apple' as longest valid word

Longest word: apple

Why: All prefixes of 'apple' exist as words. 'apply' also qualifies (all prefixes including 'appl' are words), but 'apple' is lexicographically smaller

Result:

root -> a* -> p* -> p* -> l* -> e* (apple)
Longest word: apple

Annotated Code

DSA Javascript

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    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() {
    let result = "";
    const dfs = (node, path) => {
      if (node !== this.root && !node.isWord) return;
      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;
  }
}

const words = ["a", "app", "ap", "apply", "apple", "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 child node if character path does not exist

node = node.children.get(char);

Advance node pointer to child node for current character

node.isWord = true;

Mark current node as end of a valid word

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

Stop DFS if current node is not root and not end of a word (prefix invalid)

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 equal length

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) because we insert N words each of length L and DFS visits nodes once

Space: O(N * L) for trie storage of all words' characters

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

Edge Cases

Empty word list

Returns empty string as no words exist

DSA Javascript

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

Words with single character only

Returns the lex smallest single character word

DSA Javascript

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

Words where some prefixes are missing

Skips words whose prefixes are not marked as words in trie

DSA Javascript

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

When to Use This Pattern

When asked to find the longest word with all prefixes present, use a trie to efficiently check prefixes and find the answer.

Common Mistakes

Mistake: Not checking if each prefix is a word before continuing DFS
Fix: Add condition to stop DFS if current node is not end of a word

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

Summary

Build a trie and find the longest word where every prefix is also a word.

Use when you need to find words with all prefixes present efficiently.

The key is to stop exploring paths where prefixes are not valid words.

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