Skip to main content

20. Implement Trie (Prefix Tree)

mediumAsked at Etsy

Build insert/search/startsWith on a trie — the exact data structure powering Etsy's search autocomplete as buyers type listing keywords.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Implement the Trie class with three operations: insert(word) inserts the string word, search(word) returns true if word is in the trie, and startsWith(prefix) returns true if any previously inserted word starts with the given prefix.

Constraints

  • 1 <= word.length, prefix.length <= 2000
  • word and prefix consist only of lowercase English letters
  • At most 3 * 10^4 calls total to insert, search, and startsWith

Examples

Example 1

Input
insert("apple"), search("apple"), search("app"), startsWith("app"), insert("app"), search("app")
Output
true, false, true, true

Example 2

Input
insert("box"), startsWith("bo"), search("bo")
Output
true, false

Approaches

1. Brute force (set)

Store all inserted words in a Set. search does Set.has(). startsWith iterates all words checking prefix match. Works but O(n) per startsWith call.

Time
O(n) per startsWith, O(1) per search
Space
O(total characters)
class Trie {
  constructor() {
    this.words = new Set();
  }
  insert(word) {
    this.words.add(word);
  }
  search(word) {
    return this.words.has(word);
  }
  startsWith(prefix) {
    for (const w of this.words) {
      if (w.startsWith(prefix)) return true;
    }
    return false;
  }
}

Tradeoff:

2. Trie node tree

Each node stores a children map (char → node) and an isEnd flag. insert walks/creates nodes character by character. search and startsWith both walk the tree; search additionally checks isEnd at the terminal node.

Time
O(m) per operation where m = word length
Space
O(total characters * 26) worst case
class TrieNode {
  constructor() {
    this.children = {};
    this.isEnd = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) node.children[ch] = new TrieNode();
      node = node.children[ch];
    }
    node.isEnd = true;
  }

  _walk(str) {
    let node = this.root;
    for (const ch of str) {
      if (!node.children[ch]) return null;
      node = node.children[ch];
    }
    return node;
  }

  search(word) {
    const node = this._walk(word);
    return node !== null && node.isEnd;
  }

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

Tradeoff:

Etsy-specific tips

Etsy's search team uses tries for autocomplete prefix matching across millions of active listings. Interviewers will ask how you'd handle case-insensitive input and Unicode — normalize to lowercase at insert/query time, and note that Unicode requires a Map instead of a fixed 26-slot array. Also be ready to extend startsWith to return all matching words via DFS.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Implement Trie (Prefix Tree) and other Etsy interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →