Trie vs Hash Map for Prefix Matching in DSA Typescript - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Prefix Search Using Trie

What is the output of the following TypeScript code that uses a Trie to find words with a given prefix?

DSA Typescript

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

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

  insert(word: string) {
    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;
  }

  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 = (currNode: TrieNode, path: string) => {
      if (currNode.isWord) results.push(path);
      for (const [ch, nextNode] of currNode.children) {
        dfs(nextNode, path + ch);
      }
    };
    dfs(node, prefix);
    return results;
  }
}

const trie = new Trie();
['apple', 'app', 'apex', 'bat', 'bath'].forEach(w => trie.insert(w));
console.log(trie.searchPrefix('ap'));

A ["apple", "apex"]

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

C ["app", "apex"]

D ["bat", "bath"]

💡 Hint

Think about all words starting with 'ap' inserted into the trie.

The trie stores words 'apple', 'app', and 'apex' starting with 'ap'. The searchPrefix method collects all words starting with the prefix 'ap'.

❓ Predict Output

intermediate

Output of Prefix Search Using Hash Map

What is the output of the following TypeScript code that uses a Hash Map to find words with a given prefix?

DSA Typescript

const words = ['app', 'apple', 'apex', 'bat', 'bath'];
const prefix = 'ap';
const result = words.filter(word => word.startsWith(prefix));
console.log(result);

A ["bat", "bath"]

B ["apple", "apex"]

C ["app", "apex"]

D ["app", "apple", "apex"]

💡 Hint

Filter words that start with the prefix 'ap'.

The filter method returns all words starting with 'ap' from the array.

🧠 Conceptual

advanced

Why Use Trie Over Hash Map for Prefix Matching?

Which of the following is the main advantage of using a Trie over a Hash Map for prefix matching in large datasets?

A Trie allows efficient prefix search with time complexity proportional to prefix length, not dataset size.

B Trie uses less memory than a Hash Map for storing all words.

C Hash Map cannot store strings as keys.

D Trie automatically sorts words alphabetically without extra steps.

💡 Hint

Consider how search time depends on prefix length vs number of words.

Trie search time depends on prefix length only, making it efficient for prefix queries in large datasets.

🧠 Conceptual

advanced

Memory Usage Comparison Between Trie and Hash Map

Which statement best describes memory usage when comparing Trie and Hash Map for storing many words?

A Hash Map uses more memory because it stores characters individually.

B Hash Map always uses less memory because it stores only full words as keys.

C Trie can use more memory due to storing nodes for each character, especially with sparse data.

D Trie uses less memory because it compresses common prefixes automatically.

💡 Hint

Think about how tries store each character as a node.

Tries store nodes for each character, which can increase memory usage if many prefixes are unique.

🔧 Debug

expert

Identify the Bug in Trie Prefix Search Implementation

Given the following TypeScript Trie prefix search code, what error will it produce when searching for prefix 'ap'?

DSA Typescript

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

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

  insert(word: string) {
    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;
  }

  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 = (currNode: TrieNode, path: string) => {
      if (currNode.isWord) results.push(path);
      for (const [ch, nextNode] of currNode.children) {
        dfs(nextNode, path + ch);
      }
    };
    dfs(node, prefix);
    return results;
  }
}

const trie = new Trie();
['apple', 'app', 'apex', 'bat', 'bath'].forEach(w => trie.insert(w));
console.log(trie.searchPrefix('ap'));

A No error; outputs ["app", "apple", "apex"]

B TypeError because node.children is undefined

C Stack overflow due to infinite recursion in dfs

D SyntaxError due to missing return statement in dfs

💡 Hint

Check how dfs is called and if recursion ends properly.

The code correctly implements dfs with base case and recursion, so no error occurs and output is correct.