Implement a Trie with Insert, Search, Prefix, and Delete

Prompt and Applicable Context

Implement a Trie storing a set of words with four operations:

• insert(word) adds a word and is idempotent when the word already exists.
• search(word) returns whether that complete word is stored.
• startsWith(prefix) returns whether that prefix path exists; for a nonempty prefix, this means at least one stored word has it.
• delete(word) removes the complete word and returns whether it existed.

Assume insert, search, and delete receive nonempty lowercase English words. startsWith also accepts the empty prefix, which returns true because this API defines the root path as the empty prefix even before any insertion. The implementation is in memory, single-threaded, and does not enumerate suggestions, rank results, persist data, or normalize Unicode. Input validation sits outside the class.

This is a representative coding-interview problem for software engineering roles. The core task is to model shared prefixes and distinguish “this path exists” from “a word ends here.” Adding deletion exposes whether the candidate truly understands that model: deleting app must preserve apple, while deleting the last unique suffix may reclaim its nodes.

What the Interviewer Evaluates

The first signal is deriving the structure from the operations. A hash set handles exact membership, but a prefix query would need to inspect stored words or maintain another index. A Trie makes each prefix a path from the root, so query cost depends on input length instead of the number of stored words.

The second signal is the terminal marker. The path for app exists after inserting apple, but search("app") remains false until that node is marked as a complete word. startsWith("app") needs only the path. One traversal helper can serve both operations while their final conditions stay distinct.

The third signal is deletion safety. Clearing a terminal marker is sufficient for logical deletion. Physical pruning is optional and may proceed upward only while the child is nonterminal and childless. This rule preserves both longer words and shorter words sharing the deleted path.

Finally, the interviewer looks for honest complexity and tests. A map-backed node avoids allocating 26 child slots at every sparse node, but map operations use their language runtime's average-performance assumptions. Deletion also keeps an O(L) path stack; claiming constant auxiliary space would contradict the code.

Questions to Clarify Before Answering

• What characters are allowed? Lowercase a-z permits a 26-slot array. Unicode, mixed case, or a sparse alphabet favors a map and may require a normalization contract.
• Are duplicate insertions counted? This problem stores a set, so a second insertion is idempotent. A multiset would need terminal and prefix counters.
• What should deletion report? It returns false for a missing word and true only when a stored complete word is removed.
• Must deletion reclaim nodes? Here it does safe pruning. If deletions are rare and memory is not constrained, clearing the terminal marker is simpler and still correct.
• Is an empty word valid? No. The empty prefix is allowed, but the empty string cannot be inserted or searched as a word in this contract.
• Are prefix results enumerated or merely detected? This API returns a boolean. Listing matches adds subtree traversal and output-sensitive cost.
• Is concurrency required? No. Concurrent reads and writes would require a synchronization or immutable-snapshot design.

30-Second Answer Framework

“I will represent each prefix as a path from one root. Every node maps the next character to a child and has an isWord flag. Insert creates missing nodes and marks the final node. Search walks the path and checks that flag; prefix search only requires the path. Delete first records the path, clears the final flag, then removes nodes backward only while they have no children and are not another word's end. Each operation is expected O(L) with map-backed children, total storage is O(C), and delete uses O(L) auxiliary space.”

Step-by-Step Deep Answer

A list or unsorted set of words makes a prefix query depend on the number of words. A sorted array can find the first possible prefix match with binary search and is attractive for a read-mostly, static dictionary, but insertion and deletion require shifting or rebuilding. A Trie pays per-character node overhead to support all four online operations directly.

Use this invariant:

For every stored word, its characters form a root-to-node path, and isWord is true at a node exactly when the path spelling that node is a stored complete word.

The invariant explains all operations. Insert extends one path and turns on its final marker. Search requires both the path and the marker. Prefix search requires only the path. Delete turns off exactly one marker and removes a suffix only when no remaining word can use it.

class TrieNode {
  readonly children = new Map<string, TrieNode>()
  isWord = false
}

class Trie {
  private readonly root = new TrieNode()

  insert(word: string): void {
    let node = this.root

    for (const character of word) {
      let child = node.children.get(character)
      if (!child) {
        child = new TrieNode()
        node.children.set(character, child)
      }
      node = child
    }

    node.isWord = true
  }

  search(word: string): boolean {
    return this.walk(word)?.isWord ?? false
  }

  startsWith(prefix: string): boolean {
    return this.walk(prefix) !== undefined
  }

  delete(word: string): boolean {
    let node = this.root
    const path: Array<[TrieNode, string, TrieNode]> = []

    for (const character of word) {
      const child = node.children.get(character)
      if (!child) return false

      path.push([node, character, child])
      node = child
    }

    if (!node.isWord) return false
    node.isWord = false

    for (let index = path.length - 1; index >= 0; index -= 1) {
      const [parent, character, child] = path[index]
      if (child.isWord || child.children.size > 0) break
      parent.children.delete(character)
    }

    return true
  }

  private walk(text: string): TrieNode | undefined {
    let node = this.root

    for (const character of text) {
      const child = node.children.get(character)
      if (!child) return undefined
      node = child
    }

    return node
  }
}

Deletion is easiest to verify with two counterexamples. If app and apple are stored, deleting app clears the marker at the second p but stops pruning because that node has child l. apple remains searchable. If app and apt are stored, deleting app removes only the final p; pruning then stops at the shared ap node because it still has child t.

Correctness follows by induction. The empty Trie satisfies the invariant. Insert changes only one path and its final marker. Search and prefix search do not mutate state. A successful delete first removes exactly the target marker. Every pruned node is nonterminal and childless, so it cannot represent a stored word or lead to one. Removing it preserves every remaining stored path; stopping at the first terminal or branching node preserves the shared prefix.

Let L be the input length and C the number of character nodes currently allocated. Under average map lookup, insert, search, and prefix search take expected O(L) time. Delete traverses forward and prunes at most the same L edges, so it is also expected O(L). The Trie uses O(C) space, bounded by the sum of distinct stored-prefix characters; delete's path uses O(L) auxiliary space.

For a fixed lowercase alphabet, TrieNode | undefined[26] gives direct indexed access and predictable per-character work, but reserves 26 references per node. A map stores only existing edges and handles a wider alphabet, with hashing and object overhead. The answer should choose based on alphabet and density, not claim one representation always wins.

Validation should check state transitions, not only one lookup. Start with startsWith("") === true, search("") === false, and deletion from an empty Trie. Insert app, apple, and apt; reinsert app; distinguish search("ap") from startsWith("ap"); delete app while preserving apple; reject a second deletion; then delete the remaining words and confirm their prefixes disappear. A randomized test can compare all operations with a simple Set<string> reference and scan the set for prefix queries.

If the requirement is only exact membership, a hash set is shorter and usually preferable. If the dictionary is static and sorted, binary search can answer existence of a prefix without node-heavy storage. If long single-child chains dominate memory, a radix tree compresses those chains at the cost of more complex split and merge logic.

High-Quality Sample Answer

“I would first confirm the alphabet, duplicate semantics, and whether deletion must reclaim memory. I will assume nonempty lowercase words, set semantics, an empty prefix that matches, and safe pruning on delete.

Each Trie node stores its outgoing character edges and a terminal flag. The root-to-node path is a prefix; the flag says whether that same path is also a complete stored word. Insert creates missing children and marks only the final node. Search checks the final flag, while startsWith only checks whether traversal succeeds.

For delete, I record each parent, edge, and child while walking the word. If the path is missing or the final node is not terminal, I return false without changing state. Otherwise I clear the marker and walk backward. I remove an edge only when its child has no children and is not terminal, stopping at the first node still needed by another word. That is what keeps apple intact when deleting app.

With map-backed children, all operations are expected O(L). Total storage is O(C) character nodes, and delete uses an O(L) path stack. I would test empty and missing cases, duplicate insertion, a word that is another word's prefix, two words that branch, and full pruning after the last word is removed. If exact lookup were the only operation, I would use a hash set instead.”

Common Mistakes

• Treat every reachable path as a word → search("app") becomes true after inserting only apple → require isWord for exact search.
• Make startsWith check isWord → valid prefixes are rejected unless separately inserted → return success when the path exists.
• Clear or remove the whole path during deletion → deleting app destroys apple → clear the terminal marker first and prune only nonterminal leaves.
• Prune past a branching node → an unrelated word such as apt disappears → stop when the child still has children.
• Prune past another terminal node → deleting a longer word removes its shorter prefix word → stop when the child is terminal.
• Return true when only the deletion path exists → deleting app after inserting only apple mutates or misreports state → require the final node to be terminal.
• Count duplicate insertions accidentally → set semantics turn into a hidden multiset → use one boolean marker or explicitly change the contract to counters.
• Claim all four operations use constant time → work grows with the input length → state expected O(L) and the map assumption.
• Claim deletion uses no extra space → the implementation stores the path for backward pruning → report O(L) auxiliary space or use a justified recursive alternative with the same stack bound.
• Always allocate 26 children → sparse or Unicode data wastes space or breaks the alphabet contract → choose array versus map after clarifying the character set.
• Use a Trie for exact lookup only → node overhead buys a prefix feature the product never uses → prefer a hash set for exact membership alone.

Follow-Up Questions and Responses

Follow-up 1: How would duplicate words and erase-one semantics change the design?

Replace isWord with wordCount, and keep prefixCount on nodes if prefix counts are queried. Insert increments counts along the path. Erase first confirms wordCount > 0, decrements the same path, and prunes only when the relevant counts reach zero. The boolean implementation cannot distinguish one insertion from five.

Follow-up 2: How would you return the top K autocomplete results?

Finding the prefix node still costs O(L), but enumerating its subtree is output- and subtree-sensitive. For low query volume, traverse and rank on demand. For high query volume, cache a bounded ranked candidate list at each node and update it on writes, trading extra memory and write amplification for lower read latency. The ranking score and tie-breaking rule must be explicit.

Follow-up 3: How would Unicode and case-insensitive matching work?

Define normalization before choosing a representation. For example, normalize to one Unicode form and apply a locale-aware case policy at both insert and query time. Iterate by the agreed unit—code points or grapheme clusters—and use map-backed edges. Normalizing only queries or only inserts creates paths that can never match.

Follow-up 4: How would you make the Trie thread-safe?

One read-write lock around the entire Trie is the simplest correct answer: insert and delete take the write lock, while search and prefix search take the read lock. Finer node locks require a fixed acquisition order and careful protection of pruning. Immutable snapshots or copy-on-write roots simplify readers when updates are infrequent.

Follow-up 5: What if memory is the limiting resource?

Measure node density first. Fixed arrays can dominate memory in sparse data, while maps carry their own object and hashing overhead. A radix tree compresses single-child chains; a ternary search tree reduces child storage; a minimal finite-state structure can compress a static dictionary further. These choices change update complexity and implementation risk.

Follow-up 6: How would wildcard or longest-prefix matching change traversal?

Longest-prefix matching walks the query while remembering the deepest terminal node, remaining linear in query length. A wildcard such as . branches to every child at that position, so worst-case work can expand with the explored subtree. The API must state wildcard syntax and whether it returns existence, one result, or all results.