Skip to main content

208. Implement Trie (Prefix Tree)

mediumAsked at Pinterest

Pinterest's search-suggest and tag-autocomplete services run on tries. Implement Trie asks you to build a prefix tree supporting insert, search, and startsWith — and the interviewer will pivot to a harder follow-up the moment yours works.

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

Source citations

Public interview reports confirming this problem appears in Pinterest loops.

  • Glassdoor (2026-Q1)— Pinterest search-team onsite reports cite Implement Trie as the data-structure-design round.
  • LeetCode Pinterest tag (2026-Q1)— On the Pinterest company-tagged problem list, often combined with Word Search II in onsite loops.

Problem

A trie (pronounced 'try') or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. Implement the Trie class: Trie() (constructor), void insert(String word), boolean search(String word), boolean startsWith(String prefix).

Constraints

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

Examples

Example 1

Input
Trie trie; trie.insert('apple'); trie.search('apple'); trie.search('app'); trie.startsWith('app'); trie.insert('app'); trie.search('app');
Output
[null,null,true,false,true,null,true]

Approaches

1. HashSet of words (brute force)

Store every inserted word in a Set. search is O(1). startsWith walks every word checking the prefix.

Time
O(1) insert/search, O(N) startsWith where N = total words
Space
O(N * L)
class TrieSet {
  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: Fails the startsWith complexity expectation. Mention it as the naive baseline, then move on.

2. Trie with per-node children map (optimal)

Each node has a Map<char, node> and an isEnd flag. Insert walks/creates nodes; search walks to the end and checks isEnd; startsWith walks to the end of the prefix and returns whether the path exists.

Time
O(L) per operation where L = word length
Space
O(total characters inserted)
class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEnd = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }
  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch);
    }
    node.isEnd = true;
  }
  _walk(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children.has(ch)) return null;
      node = node.children.get(ch);
    }
    return node;
  }
  search(word) {
    const node = this._walk(word);
    return node !== null && node.isEnd;
  }
  startsWith(prefix) {
    return this._walk(prefix) !== null;
  }
}

Tradeoff: Per-operation O(L), independent of how many words are inserted. The Map-of-children version handles unicode trivially; for lowercase-only inputs you can use a length-26 array for ~2x speedup at the cost of memory.

Pinterest-specific tips

Pinterest's search team interviewers always pivot from Implement Trie to a follow-up: 'add a delete() operation that prunes orphan nodes,' or 'add wildcard search (LeetCode 211),' or 'add the top-K autocomplete cache.' Anticipate this — when your basic trie works, immediately volunteer 'I can extend this to support X, want me to keep going?' That signals you know Pinterest doesn't ask trie as the FINAL problem.

Common mistakes

  • Treating search and startsWith as identical — they must differ on isEnd.
  • Forgetting the isEnd flag entirely — without it, search('app') after only inserting 'apple' returns true incorrectly.
  • Using a single Map<word, ...> instead of a tree — that's not a trie, even if it has the same API.
  • Confusing prefix and word length in O() analysis.

Follow-up questions

An interviewer at Pinterest may pivot to one of these next:

  • Add delete(word) that prunes nodes that are no longer needed.
  • Wildcard search (LeetCode 211: Design Add and Search Words Data Structure).
  • Add an autocomplete(prefix, k) that returns the K most-frequent completions.
  • Word Search II (LeetCode 212) — trie + DFS on a 2D grid.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Map vs array for children — which is expected?

Map is more flexible (unicode) and saves memory if branching is sparse. Array of size 26 is faster for English-only inputs. State the tradeoff out loud, then pick one.

Why does Pinterest specifically like tries?

Search-suggest, tag-autocomplete, and even some recommendation features (board/topic hierarchies) all map naturally to prefix trees. The trie pattern transfers across multiple Pinterest product surfaces.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →