FrontendPro
Sign inBuy

146Implement an autocomplete search engine using a Trie

hardAbout 60 minutesCodingFreetriedata-structuresautocompleteheaps

Problem

Implement a Trie class that powers search-box suggestions:

  • insert(word, weight = 1): add a word, or add weight to an existing word's score (for example its search count).
  • search(word): true if the exact word was inserted.
  • startsWith(prefix): true if any inserted word starts with prefix.
  • delete(word): remove the word and return true (or false if absent). Remove nodes that no longer lead to any word.
  • suggest(prefix, limit = 5): up to limit words starting with prefix, highest score first, ties in alphabetical order.
  • size: the number of distinct words.

Everything is case-insensitive: store and compare lower-case. It must stay fast with 50,000 words.

const trie = new Trie();
trie.insert("react", 50);
trie.insert("redux", 20);
trie.insert("react native", 30);
trie.suggest("re"); // ["react", "react native", "redux"]

Try it yourself

Write your solution, run it, then submit to check it against the tests.

solution.jsJavaScript

Press Run or ⌘ Enter to execute your code.

Video walkthrough

Stuck? Watch someone solve it, then try again on your own.

Implement Trie (Prefix Tree) - Leetcode 208NeetCode on YouTubeOpen on YouTube

Step by step

Build the solution one idea at a time.

  1. 1

    Nodes are maps of characters

    Each node has children: Map<char, node>, plus end (is a word ending here) and weight. A shared prefix is stored once, which is why lookups cost O(length of the prefix), whatever the number of words.

  2. 2

    insert, search, startsWith

    Walk the characters, creating nodes on insert. search requires the final node to have end; startsWith only requires the node to exist.

  3. 3

    delete with pruning

    Walk down while remembering the path. Unmark end, then walk back up and delete child nodes that have no children and are not word ends. Otherwise dead branches make startsWith lie.

  4. 4

    suggest: find the prefix node, then collect

    From the prefix node, DFS through the subtree and collect (word, weight) pairs. Keep only the best limit (a small sorted array or a min-heap of size limit) so you never sort the whole subtree.

  5. 5

    Order consistently

    Sort by weight descending, then alphabetically. Deterministic ordering matters for tests, caching and users (suggestions should not jump around between keystrokes).

Approach

A character trie where each word's end node stores its score. Prefix queries jump straight to the prefix node; suggestions come from a DFS of that subtree with a bounded top-k selection.

Solution

class Trie {
  #root = { children: new Map(), end: false, weight: 0 };
  #size = 0;

  #walk(text) {
    let node = this.#root;
    for (const ch of text.toLowerCase()) {
      node = node.children.get(ch);
      if (!node) return null;
    }
    return node;
  }

  insert(word, weight = 1) {
    let node = this.#root;
    for (const ch of word.toLowerCase()) {
      if (!node.children.has(ch)) node.children.set(ch, { children: new Map(), end: false, weight: 0 });
      node = node.children.get(ch);
    }
    if (!node.end) {
      node.end = true;
      this.#size++;
    }
    node.weight += weight;
  }

  search(word) {
    return this.#walk(word)?.end === true;
  }

  startsWith(prefix) {
    return this.#walk(prefix) !== null;
  }

  delete(word) {
    const path = [this.#root];
    const chars = [...word.toLowerCase()];
    for (const ch of chars) {
      const next = path[path.length - 1].children.get(ch);
      if (!next) return false;
      path.push(next);
    }
    const last = path[path.length - 1];
    if (!last.end) return false;
    last.end = false;
    last.weight = 0;
    this.#size--;
    for (let i = chars.length; i > 0; i--) {
      const node = path[i];
      if (node.end || node.children.size > 0) break;
      path[i - 1].children.delete(chars[i - 1]);
    }
    return true;
  }

  suggest(prefix, limit = 5) {
    const start = this.#walk(prefix);
    if (!start || limit <= 0) return [];
    const better = (a, b) => b.weight - a.weight || (a.word < b.word ? -1 : a.word > b.word ? 1 : 0);
    const top = []; // kept sorted, at most `limit` entries
    const stack = [[start, prefix.toLowerCase()]];
    while (stack.length) {
      const [node, word] = stack.pop();
      if (node.end) {
        const candidate = { word, weight: node.weight };
        if (top.length < limit || better(candidate, top[top.length - 1]) < 0) {
          let i = top.length;
          while (i > 0 && better(candidate, top[i - 1]) < 0) i--;
          top.splice(i, 0, candidate);
          if (top.length > limit) top.pop();
        }
      }
      for (const [ch, child] of node.children) stack.push([child, word + ch]);
    }
    return top.map((entry) => entry.word);
  }

  get size() {
    return this.#size;
  }
}

Complexity

Time: insert, search, startsWith and delete are O(L) for length L. suggest is O(P + S × k) for prefix length P, S nodes under the prefix and limit k (k is small). Space: O(total characters stored), shared across common prefixes.

Edge cases

  • search("app") is false when only "apple" was inserted, while startsWith("app") is true.
  • Inserting a word twice adds to its score but counts it once in size.
  • Deleting "apple" keeps "app" if both exist, and removes the dead branch otherwise.
  • An empty prefix suggests from all words.
  • Upper-case input matches lower-case entries.

Follow-up questions

Answer each one out loud first, then reveal the model answer.