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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Longest Word Found Using Trie

What is the output of the following TypeScript code that builds a Trie from a list of words and finds the longest word where all prefixes are also words in the list?

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEnd: 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.isEnd = true;
  }

  longestWord(): string {
    let result = "";
    const dfs = (node: TrieNode, path: string): void => {
      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]))) {
        if (child.isEnd) {
          dfs(child, path + char);
        }
      }
    };
    dfs(this.root, "");
    return result;
  }
}

const words = ["a", "app", "ap", "apply", "apple", "appl", "b", "ban", "banana"];
const trie = new Trie();
for (const w of words) {
  trie.insert(w);
}
console.log(trie.longestWord());

A "apple"

B "apply"

C "appl"

D "banana"

💡 Hint

Think about which word has all its prefixes present in the list and is the longest.

The code builds a Trie and searches for the longest word such that every prefix of the word is also a word in the list. Among the given words, "apple" has prefixes "a", "ap", "app", "appl" all present. "apply" is not valid because "appl" is present but "apply" is not marked as end in the Trie (not inserted as a complete word). "banana" is longer but prefixes like "banan" are missing.

🧠 Conceptual

intermediate

Understanding Trie Node Structure

Which of the following best describes the purpose of the 'isEnd' property in a Trie node when finding the longest word in a dictionary?

A It points to the parent node in the Trie.

B It counts how many words pass through this node.

C It stores the character value of the node.

D It marks the node as the end of a valid word in the dictionary.

💡 Hint

Think about how the Trie knows a word ends at a node.

The 'isEnd' boolean indicates that the path from the root to this node forms a complete word in the dictionary. This helps in checking if prefixes are valid words.

🔧 Debug

advanced

Identify the Bug in Trie Longest Word Search

The following code attempts to find the longest word in a dictionary using a Trie, but it returns an empty string. What is the bug?

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEnd: 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.isEnd = true;
  }

  longestWord(): string {
    let result = "";
    const dfs = (node: TrieNode, path: string): void => {
      if (path.length > result.length || (path.length === result.length && path < result)) {
        result = path;
      }
      for (const [char, child] of node.children.entries()) {
        if (child.isEnd) {
          dfs(child, path + char);
        }
      }
    };
    dfs(this.root, "");
    return result;
  }
}

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

A The root node's isEnd is false, so DFS starts from a node that is not a valid prefix, causing no updates to result.

B The DFS does not sort children, so traversal order is random and may miss the lexicographically smallest word.

C The insert method does not mark the last node as isEnd = true, so no words are recognized as complete.

D The DFS does not check if the current node is the root before updating the result, causing empty string to be returned.

💡 Hint

Consider what happens at the root node and how the DFS updates the result.

The DFS starts from the root node which has isEnd = false. Since the DFS only continues down children nodes that have isEnd = true, and the root is not marked as a word, the initial call does not update the result. The root should be considered as a valid starting point or marked as isEnd = true to allow traversal.

📝 Syntax

advanced

Identify Syntax Error in Trie Implementation

Which option contains a syntax error that will prevent the TypeScript Trie code from compiling?

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEnd: 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.isEnd = true;
  }

  longestWord(): string {
    let result = "";
    const dfs = (node: TrieNode, path: string): void => {
      if (path.length > result.length || (path.length === result.length && path < result)) {
        result = path;
      }
      for (const [char, child] of [...node.children.entries()].sort()) {
        if (child.isEnd) {
          dfs(child, path + char);
        }
      }
    };
    dfs(this.root, "");
    return result;
  }
}

A Missing semicolon after 'node.isEnd = true' in insert method.

B Using 'sort()' directly on Map entries without a compare function causes a syntax error.

C The arrow function in dfs is missing a return type annotation.

D The exclamation mark '!' after get(char) is invalid syntax in TypeScript.

💡 Hint

Check how sorting is applied to Map entries in TypeScript.

Calling sort() on an array of Map entries without a compare function is valid syntax but may not sort as expected. However, in TypeScript, sorting Map entries requires a compare function to avoid errors. The other options are valid syntax: semicolons are optional, arrow functions can omit return type, and '!' is a valid non-null assertion operator.

🚀 Application

expert

Longest Word with All Prefixes Present - Result Count

Given the following list of words inserted into a Trie, how many words in the list qualify as the longest word where all prefixes are also present in the dictionary?

DSA Typescript

const words = ["a", "ap", "app", "appl", "apple", "apply", "b", "ban", "bana", "banan", "banana"];
// Assume Trie insertion and longest word logic as usual.

A 1

B 3

C 2

D 4

💡 Hint

Check which words have all prefixes present and are the longest among them.

Words "apple" and "banana" both have all prefixes present in the list. "apply" is invalid because "appl" is present but "apply" is not marked as a complete word in the dictionary (assuming it is). Here, "apply" is present, but "appl" is also present, so "apply" qualifies. So the longest words with all prefixes are "apple" and "banana" (both length 5 and 6 respectively). So count is 2.