Skip to main content

22. Implement Trie (Prefix Tree)

mediumAsked at Box

Build a prefix tree supporting insert, search, and startsWith — the same data structure Box uses to power the instant path-autocomplete in their Drive search bar as users type folder and file names.

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

Problem

Implement the Trie class with the following methods: Trie() initializes the trie. insert(word) inserts the string word into the trie. search(word) returns true if word is in the trie (i.e., was inserted before), and false otherwise. startsWith(prefix) returns true if there is a previously inserted word that has the prefix as a prefix, and false otherwise.

Constraints

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

Examples

Example 1

Input
Trie(); insert("apple"); search("apple"); search("app"); startsWith("app"); insert("app"); search("app")
Output
[null,null,true,false,true,null,true]

Explanation: "app" is not found until it is explicitly inserted, but startsWith("app") is true as soon as "apple" is inserted.

Approaches

1. Brute force — Set-based

Store every inserted word in a Set; for startsWith, scan the set for any word beginning with the prefix.

Time
O(n * k) for startsWith
Space
O(total characters)
class Trie {
  constructor() { this.words = new Set(); }
  insert(word) { this.words.add(word); }
  search(word) { return this.words.has(word); }
  startsWith(prefix) {
    for (const w of this.words) {
      if (w.startsWith(prefix)) return true;
    }
    return false;
  }
}

Tradeoff:

2. Optimal — Trie node array

Each node holds a 26-slot children array and an isEnd flag. insert/search/startsWith all traverse in O(k) where k is string length.

Time
O(k) per operation
Space
O(ALPHABET * total nodes)
class TrieNode {
  constructor() {
    this.children = new Array(26).fill(null);
    this.isEnd = false;
  }
}

class Trie {
  constructor() { this.root = new TrieNode(); }
  _charIdx(c) { return c.charCodeAt(0) - 97; }
  insert(word) {
    let node = this.root;
    for (const c of word) {
      const i = this._charIdx(c);
      if (!node.children[i]) node.children[i] = new TrieNode();
      node = node.children[i];
    }
    node.isEnd = true;
  }
  _traverse(str) {
    let node = this.root;
    for (const c of str) {
      const i = this._charIdx(c);
      if (!node.children[i]) return null;
      node = node.children[i];
    }
    return node;
  }
  search(word) {
    const node = this._traverse(word);
    return node !== null && node.isEnd;
  }
  startsWith(prefix) {
    return this._traverse(prefix) !== null;
  }
}

Tradeoff:

Box-specific tips

Box interviewers will probe whether you can extend startsWith to return all matching paths — the realistic use case for their search bar. Walk through how you would DFS from the prefix node to collect suggestions, keeping a results limit like a real-world autocomplete. Mentioning that Box indexes millions of folder paths and needs sub-millisecond prefix queries ties the theory directly to the product.

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

Practice these live with InterviewChamp.AI →