Implement Trie (Prefix Tree)

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

• Trie() Initializes the trie object.
• insert(word) Inserts the string word into the trie.
• search(word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
• startsWith(prefix) Returns true if there is a previously inserted string that has prefix as a prefix, and false otherwise.

Testing harness — dispatcher convention

Because the test runner invokes a single function rather than instantiating a class, you must expose your Trie through a dispatcher named trieOperations(operations). operations is an array of [op, ...args] tuples. The dispatcher constructs a fresh Trie and returns an array of results, one per operation:

• For ['insert', word], push null.
• For ['search', word], push the boolean result.
• For ['startsWith', prefix], push the boolean result.

Example:

function trieOperations(operations) {
  const trie = new Trie();
  const results = [];
  for (const [op, ...args] of operations) {
    if (op === 'insert') { trie.insert(args[0]); results.push(null); }
    else if (op === 'search') { results.push(trie.search(args[0])); }
    else if (op === 'startsWith') { results.push(trie.startsWith(args[0])); }
  }
  return results;
}

So a test input like [['insert','apple'], ['search','apple'], ['search','app'], ['startsWith','app'], ['insert','app'], ['search','app']] should return [null, true, false, true, null, true].