Prefix Search Using Trie in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Prefix Search Result

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

DSA Typescript

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

  searchPrefix(prefix: string): string[] {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) {
        return [];
      }
      node = node.children.get(char)!;
    }
    const results: string[] = [];
    const dfs = (currentNode: TrieNode, path: string) => {
      if (currentNode.isEndOfWord) {
        results.push(path);
      }
      for (const [char, childNode] of currentNode.children) {
        dfs(childNode, path + char);
      }
    };
    dfs(node, prefix);
    return results;
  }
}

const trie = new Trie();
trie.insert("apple");
trie.insert("app");
trie.insert("apex");
trie.insert("bat");
trie.insert("bath");
const result = trie.searchPrefix("ap");
console.log(result);

A ["app", "apple", "apex"]

B ["apple", "app", "apex"]

C ["apex", "app", "apple"]

D ["app", "apex"]

💡 Hint

Think about how the DFS collects words in alphabetical order based on children map iteration.

The DFS visits children in insertion order of Map keys, which in JavaScript/TypeScript preserves insertion order. Since 'app' was inserted before 'apple' and 'apex', the results array collects words in the order: 'app', 'apple', 'apex'.

🧠 Conceptual

intermediate

Number of Words with Given Prefix

If a Trie contains the words ["cat", "car", "cart", "dog", "dove"], how many words start with the prefix "car"?

A 0

B 2

C 3

D 1

💡 Hint

Count all words that begin exactly with 'car'.

The words starting with 'car' are 'car' and 'cart', so there are 2 words.

🔧 Debug

advanced

Identify the Bug in Trie Insertion

What error will occur when running this TypeScript code snippet for inserting a word into a Trie?

DSA Typescript

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

const trie = new Trie();
trie.insert("hello");

A No error, runs correctly

B SyntaxError: Unexpected token

C ReferenceError: node is not defined

D TypeError: Cannot read property 'isEndOfWord' of undefined

💡 Hint

Check the return type of Map.get and how it's used.

Map.get returns TrieNode | undefined. Without the non-null assertion operator (!), node can become undefined, causing a TypeError when accessing isEndOfWord.

📝 Syntax

advanced

Correct Syntax for DFS in Trie Search

Which option correctly defines the DFS function inside the searchPrefix method to collect all words starting with a prefix?

DSA Typescript

dfs = (currentNode: TrieNode, path: string) => {
  if (currentNode.isEndOfWord) {
    results.push(path);
  }
  for (const [char, childNode] of currentNode.children) {
    dfs(childNode, path + char);
  }
};

A

function dfs(currentNode: TrieNode, path: string) {
  if (currentNode.isEndOfWord) {
    results.push(path);
  }
  for (const [char, childNode] of currentNode.children) {
    dfs(childNode, path + char);
  }
}

B

dfs(currentNode: TrieNode, path: string) => {
  if (currentNode.isEndOfWord) {
    results.push(path);
  }
  for (const [char, childNode] of currentNode.children) {
    dfs(childNode, path + char);
  }
};

C

const dfs = (currentNode: TrieNode, path: string) => {
  if (currentNode.isEndOfWord) {
    results.push(path);
  }
  for (const [char, childNode] of currentNode.children) {
    dfs(childNode, path + char);
  }
};

D

const dfs = function(currentNode: TrieNode, path: string) {
  if (currentNode.isEndOfWord) {
    results.push(path);
  }
  for (const [char, childNode] of currentNode.children) {
    dfs(childNode, path + char);
  }
};

💡 Hint

Arrow functions with const are common for nested functions in TypeScript.

Option C correctly uses a const arrow function with proper syntax. Option C is valid but uses function declaration, which is also correct but less common inside methods. Option C is invalid syntax. Option C is valid but less idiomatic than A.

🚀 Application

expert

Find All Words with Prefix and Sort Alphabetically

Given a Trie with words inserted in any order, which code modification ensures that searchPrefix returns all words starting with the prefix sorted alphabetically?

DSA Typescript

searchPrefix(prefix: string): string[] {
  let node = this.root;
  for (const char of prefix) {
    if (!node.children.has(char)) {
      return [];
    }
    node = node.children.get(char)!;
  }
  const results: string[] = [];
  const dfs = (currentNode: TrieNode, path: string) => {
    if (currentNode.isEndOfWord) {
      results.push(path);
    }
    for (const [char, childNode] of currentNode.children) {
      dfs(childNode, path + char);
    }
  };
  dfs(node, prefix);
  return results;
}

A Modify DFS to visit children in alphabetical order by sorting keys before recursion.

B Change Map to a JavaScript object and iterate keys sorted alphabetically.

C Use a PriorityQueue to store words during DFS and dequeue all at the end.

D Sort the results array before returning: return results.sort();

💡 Hint

Think about controlling the order of traversal rather than sorting after collection.

Sorting keys before recursion ensures DFS visits children in alphabetical order, so results are collected sorted without extra sorting step. Option A sorts after collection but is less efficient. Option A changes data structure but does not guarantee order. Option A adds complexity.