Solution

You're building a class that stores a set of strings as a character-keyed tree — every edge is one character, every path from the root spells out a stored word, and a small flag at each node tells you "yes, the string spelled by the path that ends here was actually inserted" versus "I'm only a stepping stone to longer words."

The problem, in plain English

A trie is what you'd build if you needed startsWith to be cheap. Storing words in an array or a Set makes "does any of my words start with 'app'?" expensive — you have to scan every word until you find one that starts with the prefix (or scan them all to confirm none does). A trie pays a one-time cost at insert time to lay every word out along a shared tree of characters; in return, every read — exact match or prefix probe — costs only as much as the input string itself.

The three methods all share the same walk: start at the root, take the edge labelled by the next character of the query, repeat. They differ only at the very end. insert writes — creating any edges that were missing. search reads — and demands the final node be marked as an end-of-word. startsWith reads — and is happy as long as the walk didn't fall off the tree.

The mental model

Picture the words app, apple, and apply laid out as one branching path. The shared a-p-p prefix lives on a single chain of three nodes — there's only one 'a' edge out of the root, only one 'p' out of that a, only one 'p' out of that. Then the chain branches: from the second p you can either stop (because app is a complete word) or continue with l, and from l you split into e (giving apple) or y (giving apply).

That isEnd flag is the single most important idea in the whole data structure. The tree shape alone tells you which character sequences are reachable from the root, but reachability is not the same as "was inserted." The path a → p → p exists as soon as you insert apple; the flag is what tells search('app') that 'app' itself was never explicitly stored, even though every character of it is sitting right there in the tree.

A first attempt

Before reaching for trees, it's tempting to keep the stored words in an array and do all three operations with Array methods. It's two lines of bookkeeping and reads like English:

class NaiveTrie {
  constructor() { this.words = []; }
  insert(word) { if (!this.words.includes(word)) this.words.push(word); }
  search(word) { return this.words.includes(word); }
  startsWith(prefix) {
    return this.words.some((w) => w.startsWith(prefix));
  }
}

This is correct, but it has one ugly scaling property: startsWith walks the entire stored array every time, and for each word it does string-prefix work proportional to the prefix length. With 100,000 stored words and a 5-character prefix, every startsWith call does roughly 500,000 character comparisons. Add a few of those calls per keystroke in an autocomplete UI and you have a noticeably laggy input box.

A trie flips the cost. Each insert does a tiny amount more work (walk the word, create missing nodes), and in return every read — exact or prefix — costs only as much as the query length. 100,000 words stored, 5-character prefix: at most 5 pointer hops. The number of stored words doesn't enter into it at all.

The working solution

class Trie {
  constructor() {
    // The root is just an empty node — a plain object with no character
    // edges yet. We deliberately do NOT mark it as an end-of-word here;
    // insert('') will set the flag on this very node.
    this.root = {};
  }

  insert(word) {
    let node = this.root;
    // for...of iterates code points correctly. word.split('') and a plain
    // for-loop over indices both split surrogate pairs into two halves,
    // so 'a😀b' would be 4 nodes instead of 3 — wrong, and
    // silent.
    for (const ch of word) {
      // Lazily create the edge if the child doesn't exist. {} is the
      // cheapest possible node — adding fields is free.
      if (!node[ch]) node[ch] = {};
      node = node[ch];
    }
    // The end-of-word sentinel. We use a single-character key '$' that
    // cannot be confused with a real character edge (we know our keys
    // are real chars from the input). Naming it `isEnd` would also work,
    // but `isEnd` collides with a hypothetical user inserting the string
    // 'isEnd' as a child key — using '$' rules that out by convention.
    node.$ = true;
  }

  search(word) {
    let node = this.root;
    for (const ch of word) {
      node = node[ch];
      // Walked off the tree — no such edge — so the word can't be stored.
      if (!node) return false;
    }
    // Reached the end of the word. Must explicitly check the flag —
    // merely reaching a node does NOT mean the word was inserted; the
    // word might just be a prefix of something longer.
    return node.$ === true;
  }

  startsWith(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      node = node[ch];
      if (!node) return false;
    }
    // The walk completed. For a non-empty prefix we created the final
    // node during some insert call, so SOME word definitely starts with
    // this prefix — return true. For the empty prefix the walk did
    // nothing; we're still at the root. "Does any inserted word start
    // with ''?" is true iff there IS an inserted word — i.e. the root
    // either has a character child or is itself end-of-word.
    if (prefix === '') {
      return node.$ === true || Object.keys(node).length > 0;
    }
    return true;
  }
}

module.exports = { Trie };

Three small shifts from the naive version do all the work. First, words share structure. Inserting apple and apply creates five nodes total, not ten — the shared a-p-p-l chain is built once and walked twice. Second, the search shape is length-of-query, not count-of-stored-words. The query string drives the walk; the trie's total size affects only how much memory is sitting unused on other branches. Third, search and startsWith are literally the same walk — only the final check differs (return node.$ === true versus return true).

The choice of '$' for the end-of-word marker deserves one note: any field name will do as long as it cannot collide with a real character key. '$' is a single character, so as long as your inputs are real-world words '$' will never appear as a child edge. If your input can be arbitrary text (including the literal $), use Object.create(null) for nodes and pick a name that's reserved (e.g. a Symbol, or Map for children with a separate boolean field on the node).

Walking through one call

Start with const t = new Trie(). t.root is {} — a fresh empty node with no children and no $ flag.

Step 1 — t.insert('apple'). Walk character by character. 'a': root['a'] is undefined, so create root['a'] = {} and descend. 'p': root.a['p'] is undefined, create it. 'p' again: a new child off the previous p. 'l': another new child. 'e': another. Then set e.$ = true. After this call the trie looks like:

{
  a: {
    p: {
      p: {
        l: {
          e: { $: true }    // ← "apple" ends here
        }
      }
    }
  }
}

Step 2 — t.insert('app'). Walk again. 'a': root['a'] already exists — descend without creating. 'p': exists, descend. 'p': exists, descend. End of word: set p.$ = true on the second p. The tree gains no new nodes — only a flag is added:

{
  a: {
    p: {
      p: { $: true,         // ← "app" ends here
        l: { e: { $: true } }
      }
    }
  }
}

This is the moment that makes the trie's promise concrete: a single node now records that both app and the path-on-the-way-to-apple end here. Storing one extra word cost us exactly one boolean.

Step 3 — t.search('app'). Walk: 'a' → 'p' → 'p'. We land on the node whose $ is true. Return node.$ === true → true.

Step 4 — t.search('appl'). Walk: 'a' → 'p' → 'p' → 'l'. We land on the l node. Its $ is undefined (we never inserted the word 'appl'). Return node.$ === true → false. This is the prefix-vs-word distinction in action: we can reach l from the root, so the path exists, but no one ever said "this is a complete stored word."

Step 5 — t.startsWith('ap'). Walk: 'a' → 'p'. The walk completes without falling off the tree. startsWith doesn't check $, so we return true. (And note: search('ap') on the same trie would walk to the same node but then check $ — and return false, because we never inserted 'ap' either.)

Gotchas

• The isEnd flag is not optional. Without it, search('app') and startsWith('app') would always return the same value — both would just check whether the path exists. The flag is the only thing that distinguishes "stored word" from "prefix of a stored word." Remove it and you've built a different (less useful) data structure.
• Use for...of, not word.split('') or a for (let i…) loop over word[i]. All three look equivalent for ASCII, but for...of iterates Unicode code points — it treats a surrogate pair (e.g. an emoji like '😀') as one character, while the other two split it into two ill-formed halves. Quiet correctness bug; the unit tests will not catch it unless you specifically include non-BMP input.
• Empty strings: the root itself stands in for the empty word. If insert('') is called, the loop body runs zero times and we set root.$ = true. search('') then walks zero characters and returns root.$ === true — exactly the right answer without special-casing. startsWith('') is the one place the empty input genuinely needs a guard: a zero-length walk leaves us at the root, and "does any inserted word start with the empty string?" is only true if there's at least one inserted word — hence the node.$ === true || Object.keys(node).length > 0 check on an otherwise-empty trie.
• Plain objects collide with prototype names. If a user inserts the word '__proto__' or 'constructor', node['__proto__'] does not store a new child — it walks up the prototype chain. The fix is to use Map for children (new Map()) or to create nodes with Object.create(null) so they have no prototype. The reference solution uses {} for brevity; flag this trade-off if you're shipping production code.
• if (!node[ch]) versus if (node[ch] === undefined). Equivalent here because trie node values are either an object or undefined. But if you ever change the shape (e.g. store something falsy in a slot), the truthy check silently breaks. Be explicit if you can.

Going further

• delete(word). Remove the isEnd flag from the word's terminal node, then walk back up pruning any nodes that have no children and no other end-of-word marker. The tricky part is not pruning a node that's still the end of a shorter stored word — e.g. deleting 'apple' from a trie that also contains 'app' must leave the a-p-p chain intact.
• wordsWithPrefix(prefix). Walk to the prefix node like startsWith, then DFS the subtree collecting every path that ends at an isEnd node. This is what powers an autocomplete dropdown — given the user's current input, return the (up to) ten matching completions.
• Compressed / Patricia trie. Long unique suffixes (e.g. the pricot tail of 'apricot' if it's the only word with that prefix) waste one node per character. A compressed trie merges any chain of single-child nodes into one node whose edge is labelled with the whole string. Same big-O for the three operations, but dramatically smaller memory footprint on real vocabularies.
• Ternary search tree. Each node has three children (less / equal / greater) instead of one per alphabet character. Slower per character than a trie but uses far less memory when the alphabet is large (e.g. arbitrary Unicode) or sparse.