Implement a Trie

Start from brute force

The obvious approach stores the words in a set. search is a membership test, and startsWith loops over every stored word calling word.startswith(prefix). It is correct, and search is fast: O(L) on average to hash a string of length L. But each startsWith costs O(N·L) for N stored words, with O(C) space for C stored characters. That is exactly the wrong cost for autocomplete, which runs a prefix query on every keystroke against a large dictionary. Precomputing a set of every prefix makes startsWith O(L), but it costs O(L²) time and space per inserted word.

The approach

A trie stores each shared prefix once: a word is a path from the root, one node per character. The reference makes every node a plain dict, root = {}, with children keyed by character and the key "$" marking that the path to this node spells a complete word. insert walks with node = node.setdefault(ch, {}), creating only the missing nodes, then sets node["$"] = True.

search and startsWith share one walk: follow node[ch] per character and set ok = False at the first missing child. Only the final check differs. startsWith returns ok, since an existing path is enough; search returns ok and "$" in node, since "app" can be a path inside "apple" without being a word. The invariant: a node carries "$" exactly when the path to it was inserted as a whole word. Each operation takes one dict step per character, so its cost depends on the string’s length, not on how many words are stored.

Walk through an example

Replaying the first example shows "app" existing as a path long before it exists as a word.

Complexity

Each operation is O(L) time for a string of length L, whatever the number of stored words, so the replay is O(total characters in ops). Space is O(C) nodes for C inserted characters, fewer when words share prefixes. The set approach costs O(N·L) per startsWith for N stored words, with O(C) space.

Edge cases to test

• A prefix that is not a word: insert "hello", then search("hell") is False and startsWith("hell") is True.
• A query longer than any stored word: insert "app", then search("apple") and startsWith("apple") are both False, because the walk falls off at "l".
• An empty trie: [["search","a"],["startsWith","a"]] returns [False, False].
• The empty string: startsWith("") is True even on an empty trie, because the walk takes no steps, while search("") stays False until "" itself is inserted, which marks the root.
• Nested words keep both markers: after inserting "car" and "card", search("car") and search("card") are both True. Inserting a word twice changes nothing.
• The "$" marker shares the key space with letters, which is safe only because words are lowercase letters: insert "a$" and the reference reports search("a") as True. A separate boolean field per node avoids the collision.

Common mistakes

• Not distinguishing “is a complete word” from “is a prefix” — that is exactly what the end-of-word flag is for.
• Conflating search (needs the end flag) with startsWith (path existence only).
• Assuming a fixed 26-letter array when the alphabet is larger — a hash map of children is more general.

Follow-ups an interviewer asks next

How do you return autocomplete suggestions for a prefix?

Walk to the prefix node exactly as startsWith does, then run a DFS below it, collecting every marked node along with the path that spells it. To return only the top k by popularity, store a count on each word’s node, or cache the best k completions at every node, trading memory for O(L) lookups.

How would you support delete?

Walk to the word’s last node and remove its end marker. Then prune on the way back up: delete a child that has no marker and no children, and stop at the first node still in use. Without pruning the trie stays correct but keeps dead branches. A per-node count of words passing through makes each pruning check O(1).

The trie uses too much memory. What are the options?

A radix tree (compressed trie) merges each chain of single-child nodes into one edge labeled with a string, which removes most nodes in a sparse trie. A fixed 26-slot array per node is fast but wastes space on empty slots; a hash map per node is the reverse. For a static dictionary, a DAWG also shares common suffixes, not only prefixes.

How would you count the stored words that start with a prefix?

Keep a counter on every node and, when inserting a word that was not already present, increment it on each node along the path. The answer for a prefix is the counter on its last node: an O(L) walk instead of a DFS over the whole subtree.

Where this shows up

Tries power autocomplete and typeahead, spell-checkers, IP routing (longest-prefix match), and dictionary lookups — anywhere you query by prefix, which a hash map fundamentally cannot do because it scatters keys with no shared structure.

Reference solution

def trie_ops(ops):
    root = {}                       # node: char -> child dict; "$" marks a word end
    out = []
    for cmd, word in ops:
        if cmd == "insert":
            node = root
            for ch in word:
                node = node.setdefault(ch, {})
            node["$"] = True        # this path spells a complete word
        elif cmd == "search":
            node = root
            ok = True
            for ch in word:
                if ch not in node:
                    ok = False
                    break
                node = node[ch]
            out.append(ok and "$" in node)   # must end on a word
        elif cmd == "startsWith":
            node = root
            ok = True
            for ch in word:
                if ch not in node:
                    ok = False
                    break
                node = node[ch]
            out.append(ok)          # path exists is enough
    return out


print(trie_ops([["insert","apple"],["search","apple"],["search","app"],
                ["startsWith","app"],["insert","app"],["search","app"]]))  # -> [True, False, True, True]

function trieOps(ops: string[][]): boolean[] {
  const root: any = {};             // char -> child; "$" marks a word end
  const out: boolean[] = [];
  for (const [cmd, word] of ops) {
    if (cmd === "insert") {
      let node = root;
      for (const ch of word) node = node[ch] || (node[ch] = {});
      node["$"] = true;             // complete word
    } else if (cmd === "search") {
      let node = root, ok = true;
      for (const ch of word) {
        if (!(ch in node)) { ok = false; break; }
        node = node[ch];
      }
      out.push(ok && "$" in node);  // must end on a word
    } else if (cmd === "startsWith") {
      let node = root, ok = true;
      for (const ch of word) {
        if (!(ch in node)) { ok = false; break; }
        node = node[ch];
      }
      out.push(ok);                 // path exists is enough
    }
  }
  return out;
}

console.log(trieOps([["insert","apple"],["search","apple"],["search","app"],
  ["startsWith","app"],["insert","app"],["search","app"]])); // -> [true,false,true,true]