Longest Word in Dictionary Using Trie in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Trie Insertion and Search

What is the output of the following code that inserts words into a Trie and searches for a prefix?

DSA Javascript

class TrieNode {
  constructor() {
    this.children = {};
    this.isEnd = false;
  }
}

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

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEnd = true;
  }

  startsWith(prefix) {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children[char]) {
        return false;
      }
      node = node.children[char];
    }
    return true;
  }
}

const trie = new Trie();
trie.insert("apple");
trie.insert("app");
console.log(trie.startsWith("app"));
console.log(trie.startsWith("apl"));

A true\nfalse

B true\ntrue

C false\nfalse

D false\ntrue

💡 Hint

Think about whether the prefix 'app' exists in the Trie after insertion.

The prefix 'app' exists because both 'app' and 'apple' were inserted. The prefix 'apl' does not exist, so startsWith returns false for it.

🧠 Conceptual

intermediate

Longest Word Construction Condition

In the problem of finding the longest word in a dictionary using a Trie, what condition must be true for a word to be considered valid for the longest word?

A The word must not share any prefix with other words

B The word must be the shortest in the dictionary

C Every prefix of the word must also be a word in the dictionary

D The word must contain at least one vowel

💡 Hint

Think about building the word step by step from smaller words.

The longest word is valid only if all its prefixes are also words in the dictionary, ensuring it can be built one character at a time.

🔧 Debug

advanced

Identify the Bug in Trie Longest Word Search

What error does the following code produce when trying to find the longest word in a Trie? class TrieNode { constructor() { this.children = {}; this.isEnd = false; } } class Trie { constructor() { this.root = new TrieNode(); } insert(word) { let node = this.root; for (const char of word) { if (!node.children[char]) { node.children[char] = new TrieNode(); } node = node.children[char]; } node.isEnd = true; } longestWord() { let result = ""; const dfs = (node, word) => { if (!node.isEnd && word.length !== 0) return; if (word.length > result.length || (word.length === result.length && word < result)) { result = word; } for (const char in node.children) { dfs(node.children[char], word + char); } }; dfs(this.root, ""); return result; } } const trie = new Trie(); ["w","wo","wor","worl","world"].forEach(w => trie.insert(w)); console.log(trie.longestWord());

A TypeError: Cannot read property 'isEnd' of undefined

B SyntaxError: Unexpected token

C Returns empty string ""

D Returns "world" correctly

💡 Hint

Check the base case and traversal logic in DFS.

The code correctly returns 'world' as the longest word because all prefixes are inserted and isEnd is checked properly.

🚀 Application

advanced

Longest Word Result After Insertions

Given the following words inserted into a Trie: ["a", "banana", "app", "appl", "ap", "apply", "apple"], what is the longest word returned by the longestWord() method that requires all prefixes to be valid words?

A "apple"

B "appl"

C "apply"

D "banana"

💡 Hint

Check which words have all prefixes present in the list.

Both "apple" and "apply" have all prefixes present, but "apple" comes before "apply" lexicographically, so it is returned.

🧠 Conceptual

expert

Why Use Trie for Longest Word in Dictionary?

Why is a Trie data structure preferred over sorting and checking prefixes directly when finding the longest word in a dictionary where all prefixes must be valid words?

A Sorting is always slower than Trie insertion

B Trie allows efficient prefix checking and incremental building of words in O(N * L) time where N is number of words and L is max length

C Trie uses less memory than arrays or hash maps

D Trie automatically sorts words lexicographically without extra code

💡 Hint

Consider how prefix checks are done repeatedly.

Trie enables fast prefix checks and incremental word building, making it efficient for this problem compared to repeated prefix checks after sorting.

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