Skip to main content

17. Implement Trie (Prefix Tree)

mediumAsked at N26

Implement a trie supporting insert, search, and startsWith. N26 maps this onto IBAN-prefix routing: every European IBAN starts with a country code plus a check digit, and a trie answers prefix lookups in O(len).

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

Problem

Implement a Trie class with insert(word), search(word) returning true if the exact word is stored, and startsWith(prefix) returning true if any stored word starts with the prefix.

Constraints

  • 1 <= word.length, prefix.length <= 2000
  • word and prefix consist of lowercase English letters
  • Up to 3 * 10^4 calls total

Examples

Example 1

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

Example 2

Input
insert("de"); startsWith("de")
Output
true

Approaches

1. Hash set of words

Store every word in a set; for startsWith iterate the set checking prefix.

Time
O(n*L) per startsWith
Space
O(n*L)
// works for search but startsWith scans all words.
// Fails under 3*10^4 mixed calls.

Tradeoff:

2. Children-map nodes

Each node holds a 26-slot children map and an isEnd flag. Walk one character at a time; absent edges short-circuit.

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

Tradeoff:

N26-specific tips

N26 likes when you note that the same trie powers their IBAN-prefix BIC lookup; tag the European country codes (DE, FR, ES, IT) explicitly to show product literacy.

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

Practice these live with InterviewChamp.AI →