89. Implement Trie (Prefix Tree)

mediumAsked at Ola

Implement a Trie supporting insert, search, and startsWith.

By Sam K., Founder, InterviewChamp.AI · Last verified 2026-05-20

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.