Skip to main content

89. Implement Trie (Prefix Tree)

mediumAsked at Ola

Implement a Trie supporting insert, search, and startsWith.

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

Problem

Implement the Trie class with insert(word), search(word), and startsWith(prefix). All inputs consist of lowercase English letters.

Constraints

  • 1 <= word.length, prefix.length <= 2000
  • Up to 3 * 10^4 calls

Examples

Example 1

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

Approaches

1. Sorted list scan

Keep a sorted list of words; binary search for search and startsWith.

Time
O(n) insert, O(log n) search
Space
O(words)
// simple but expensive insert; not what's asked

Tradeoff:

2. Nested map

Each node is a map from char to next node plus an end flag.

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) { if (!n[c]) n[c] = {}; n = n[c]; }
    n.end = true;
  }
  search(word) {
    let n = this.root;
    for (const c of word) { if (!n[c]) return false; n = n[c]; }
    return !!n.end;
  }
  startsWith(prefix) {
    let n = this.root;
    for (const c of prefix) { if (!n[c]) return false; n = n[c]; }
    return true;
  }
}

Tradeoff:

Ola-specific tips

Ola interviewers like clean trie code; tie it to autocompletion in the rider app's destination-search box across millions of saved addresses.

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

Practice these live with InterviewChamp.AI →