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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Prefix Search Using Trie

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

DSA Javascript

class TrieNode {
  constructor() {
    this.children = {};
    this.isWord = 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.isWord = true;
  }

  startsWith(prefix) {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children[char]) {
        return [];
      }
      node = node.children[char];
    }
    const results = [];
    const dfs = (currNode, path) => {
      if (currNode.isWord) {
        results.push(path);
      }
      for (const c in currNode.children) {
        dfs(currNode.children[c], path + c);
      }
    };
    dfs(node, prefix);
    return results;
  }
}

const trie = new Trie();
['cat', 'car', 'cart', 'dog', 'dove'].forEach(word => trie.insert(word));
console.log(trie.startsWith('car'));

A ["car", "cart"]

B ["cat", "car", "cart"]

C []

D ["cart"]

💡 Hint

Think about which words start exactly with the prefix 'car'.

The Trie startsWith method finds all words starting with 'car'. 'car' and 'cart' start with 'car', but 'cat' does not because it differs at the third character.

🧠 Conceptual

intermediate

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?

A Hash Map can store duplicate keys which Trie cannot.

B Hash Map uses less memory than Trie for storing prefixes.

C Trie allows efficient prefix search without checking every key explicitly.

D Trie requires less code to implement than Hash Map.

💡 Hint

Consider how prefix search works in both data structures.

Trie stores characters in a tree structure allowing prefix search by traversing nodes, while Hash Map requires checking all keys or additional indexing.

❓ Predict Output

advanced

Output of Prefix Search Using Hash Map

What is the output of the following JavaScript code that uses a Hash Map (object) to find words with a given prefix?

DSA Javascript

const words = ['apple', 'app', 'apricot', 'banana', 'bat'];
const wordMap = {};
words.forEach(word => { wordMap[word] = true; });

function findPrefix(prefix) {
  const results = [];
  for (const word in wordMap) {
    if (word.startsWith(prefix)) {
      results.push(word);
    }
  }
  return results;
}

console.log(findPrefix('ap'));

A ["apple", "app", "apricot"]

B ["apple", "app"]

C ["apricot"]

D []

💡 Hint

Check which words start with 'ap'.

The function iterates all keys and collects those starting with 'ap'. 'apple', 'app', and 'apricot' all start with 'ap'.

🔧 Debug

advanced

Identify the Error in Trie Insertion

What error will the following code produce when inserting words into a Trie?

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.get(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char);
    }
    node.isWord = true;
  }
}

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

A TypeError: node.children[char] is not a function

B SyntaxError: Unexpected token

C No error, code runs correctly

D TypeError: node.children[char] is undefined

💡 Hint

Check how children are accessed when children is a Map.

children is a Map, so node.children[char] is undefined because Map uses get() method, not bracket notation.

🧠 Conceptual

expert

Time Complexity Comparison for Prefix Search

Which statement correctly compares the time complexity of prefix search in a Trie versus a Hash Map storing N words each of average length L?

A Trie prefix search is O(1), Hash Map prefix search is O(L)

B Trie prefix search is O(L), Hash Map prefix search is O(N * L)

C Trie prefix search is O(N), Hash Map prefix search is O(L)

D Both Trie and Hash Map prefix searches are O(N * L)

💡 Hint

Consider how many characters and words are checked in each data structure.

Trie prefix search traverses nodes for each character in prefix (O(L)). Hash Map requires checking all N words for prefix match (O(N * L)).