Skip to main content

17. Implement Trie (Prefix Tree)

mediumAsked at Brex

Build a prefix tree supporting insert, search, and startsWith — tests data structure design skills relevant to Brex's merchant category autocomplete and rules-engine keyword matching.

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

Problem

Implement a Trie class with insert(word), search(word) that returns true if the exact word exists, and startsWith(prefix) that returns true if any word in the trie starts with the given prefix.

Constraints

  • 1 <= word.length, prefix.length <= 2000
  • word and prefix consist of lowercase English letters only
  • At most 3 * 10^4 calls total to insert, search, startsWith

Examples

Example 1

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

Example 2

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

Approaches

1. Hash map per node

Each TrieNode stores a map of character to child node plus an isEnd boolean.

Time
O(L) per op
Space
O(ALPHABET * N * L)
class TrieNode { constructor() { this.children = {}; this.isEnd = false; } }
// insert: walk/create nodes; search: walk + check isEnd; startsWith: walk only

Tradeoff:

2. Array-indexed children (26-slot)

Use a fixed 26-element array for children to avoid hash overhead. Constant-time character lookup makes each operation strictly O(L) with better cache behavior.

Time
O(L) per op
Space
O(26 * N * L)
class TrieNode {
  constructor() { this.children = new Array(26).fill(null); this.isEnd = false; }
}
class Trie {
  constructor() { this.root = new TrieNode(); }
  _idx(c) { return c.charCodeAt(0) - 97; }
  insert(word) {
    let node = this.root;
    for (const c of word) {
      const i = this._idx(c);
      if (!node.children[i]) node.children[i] = new TrieNode();
      node = node.children[i];
    }
    node.isEnd = true;
  }
  _walk(s) {
    let node = this.root;
    for (const c of s) { node = node.children[this._idx(c)]; if (!node) return null; }
    return node;
  }
  search(word) { const n = this._walk(word); return !!n && n.isEnd; }
  startsWith(prefix) { return !!this._walk(prefix); }
}

Tradeoff:

Brex-specific tips

Brex asks about fintech infrastructure, multi-currency handling, and spend management algorithms. Expect LeetCode-style DSA focused on hash maps, sorting, and dynamic programming.

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

Practice these live with InterviewChamp.AI →