Skip to main content

20. Implement Trie (Prefix Tree)

mediumAsked at Baidu

Build a trie supporting insert, search, and startsWith on lowercase ASCII words.

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

Problem

Implement a Trie with insert(word), search(word), and startsWith(prefix). search returns true only for exact words inserted, while startsWith returns true if any inserted word begins with the prefix.

Constraints

  • 1 <= word.length, prefix.length <= 2000
  • Only lowercase English letters
  • Up to 3 * 10^4 operations

Examples

Example 1

Input
insert('apple'); search('apple');
Output
true

Example 2

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

Approaches

1. Sorted array of words

Store words in a sorted array; search and startsWith do binary search.

Time
O(log n * L) per query
Space
O(total chars)
// Insert is O(n) due to splice; doesn't scale to 30k inserts.
// Fine for static dictionaries but interviewer is asking for a trie.

Tradeoff:

2. Node-per-char trie

Each node has up to 26 children plus an isEnd flag; walk character by character.

Time
O(L) per op
Space
O(total chars)
class Trie {
  constructor() { this.root = {}; }
  insert(word) {
    let n = this.root;
    for (const c of word) n = n[c] = n[c] || {};
    n.end = true;
  }
  _find(prefix) {
    let n = this.root;
    for (const c of prefix) { if (!n[c]) return null; n = n[c]; }
    return n;
  }
  search(word) { const n = this._find(word); return !!(n && n.end); }
  startsWith(prefix) { return !!this._find(prefix); }
}

Tradeoff:

Baidu-specific tips

Baidu literally powers query rewriting and search-suggest off tries, so be ready to discuss compression to radix tries and memory cost per node for 100M+ vocabulary scale.

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 Baidu interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →