Skip to main content

90. Implement Trie (Prefix Tree)

mediumAsked at Vercel

Implement a Trie with insert, search, and startsWith. Vercel asks this because Tries are the natural data structure for their route-segment matching — each path segment becomes a node, and prefix-search is exactly what the router does on every request.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel routing-team onsite; very likely.
  • Blind (2026-Q1)— Mentioned as the most Vercel-specific structure.

Problem

A trie is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker. Implement the Trie class: Trie(), insert(word), search(word), startsWith(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 will be made.

Examples

Example 1

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Approaches

1. Single Set of inserted words + linear prefix scan

Set of words; startsWith does Array.from(set).some(prefix check).

Time
O(N * L) per startsWith
Space
O(total chars)
// O(N) per startsWith. Vercel rejects this.

Tradeoff: Slow on startsWith.

2. Trie node with children map (optimal)

Each node has children (Map or array of 26) and isEnd flag. Insert walks/creates nodes; search walks and checks isEnd; startsWith walks and returns true if walk completes.

Time
O(L) per op
Space
O(total chars in trie)
class Trie {
  constructor() { this.root = { children: new Map(), end: false }; }
  insert(word) {
    let node = this.root;
    for (const c of word) {
      if (!node.children.has(c)) node.children.set(c, { children: new Map(), end: false });
      node = node.children.get(c);
    }
    node.end = true;
  }
  _walk(s) {
    let node = this.root;
    for (const c of s) {
      if (!node.children.has(c)) return null;
      node = node.children.get(c);
    }
    return node;
  }
  search(word) { const n = this._walk(word); return n !== null && n.end; }
  startsWith(prefix) { return this._walk(prefix) !== null; }
}

Tradeoff: O(L) per operation. Using a Map allows arbitrary alphabets; for lowercase-only, an array of 26 is faster.

Vercel-specific tips

Vercel grades the structure. Bonus signal: offering the array-of-26 optimization for the constrained alphabet, mentioning compact tries (radix tree) for memory savings, and connecting this to actual route matching where path segments (not characters) are the trie keys.

Common mistakes

  • Forgetting the isEnd flag — search(prefix) would return true.
  • Using a shared root reference across instances by accident (declaring in prototype).
  • Iterating the Map values to find a child — use .has and .get for O(1).

Follow-up questions

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

  • Word Search II (LC 212, hard) — use Trie to prune grid search.
  • Add and Search Word (LC 211) — wildcard '.' in search.
  • Autocomplete System (LC 642) — Trie + frequency tracking.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why isEnd?

Without it, search('app') after inserting 'apple' returns true incorrectly. The flag marks 'a complete word ends here', distinguishing full words from mere prefixes.

Map vs array of 26?

Map is more flexible (any alphabet). Array is faster for fixed lowercase (no hash lookup). For 26 letters, the array version is meaningfully faster in JS.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →