Overview

A Trie (pronounced "try"), also called a prefix tree, is a tree data structure used to efficiently store and retrieve keys in a dataset of strings.

Your solution will be tested by processing a list of operations. Implement processTrie(operations) where each operation is one of:

• ["insert", word] — inserts the string word into the trie.
• ["search", word] — returns true if the exact string word is in the trie, false otherwise.
• ["startsWith", prefix] — returns true if there is any string in the trie that starts with the given prefix, false otherwise.

Return an array of results (null for insert, boolean for search/startsWith).

Constraints

• 1 ≤ word.length, prefix.length ≤ 2000
• word and prefix consist only of lowercase English letters.
• At most 30,000 calls total.

Examples

processTrie([
  ["insert", "apple"],
  ["search", "apple"],      // → true
  ["search", "app"],        // → false
  ["startsWith", "app"],    // → true
  ["insert", "app"],
  ["search", "app"],        // → true
]);
// → [null, true, false, true, null, true]

Notes

• Each trie node has up to 26 children (one per letter) and a boolean flag marking end-of-word.
• Insert: walk the trie creating nodes as needed, mark the last node.
• Search: walk the trie; return true only if the final node exists and is marked as end-of-word.
• StartsWith: walk the trie; return true if the walk completes without a missing node.

Solution

function processTrie(operations) {
  const root = {};
  const results = [];

  function insert(word) {
    let node = root;
    for (const ch of word) {
      if (!node[ch]) node[ch] = {};
      node = node[ch];
    }
    node.$ = true;
  }

  function search(word) {
    let node = root;
    for (const ch of word) {
      if (!node[ch]) return false;
      node = node[ch];
    }
    return node.$ === true;
  }

  function startsWith(prefix) {
    let node = root;
    for (const ch of prefix) {
      if (!node[ch]) return false;
      node = node[ch];
    }
    return true;
  }

  for (const op of operations) {
    if (op[0] === "insert") { insert(op[1]); results.push(null); }
    else if (op[0] === "search") { results.push(search(op[1])); }
    else { results.push(startsWith(op[1])); }
  }

  return results;
}

Resources

• Implement Trie — LeetCode
• Trie — Wikipedia