Skip to main content

24. Implement Trie (Prefix Tree)

mediumAsked at Quora

Build a prefix tree that supports insert, search, and startsWith — Quora's autocomplete engine is a production trie; they ask you to implement one from scratch to verify you understand the branching mechanics under the hood.

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

Problem

Implement the Trie class: Trie() initialises the trie. void insert(String word) inserts a word. boolean search(String word) returns true if the exact word exists. boolean startsWith(String prefix) returns true if any word starts with the prefix.

Constraints

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

Examples

Example 1

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

Approaches

1. Array-indexed children (26-slot)

Each node holds an array of 26 child pointers (one per letter) and an isEnd flag. Fixed array means O(1) character lookup.

Time
O(L) per operation where L = word length
Space
O(total characters * 26)
class TrieNode {
  constructor() {
    this.children = new Array(26).fill(null);
    this.isEnd = false;
  }
}

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

Tradeoff:

2. Hash-map children (Unicode-friendly)

Replace the fixed 26-slot array with a Map so the trie handles arbitrary character sets — essential for Quora's multilingual platform.

Time
O(L) per operation
Space
O(total characters)
class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEnd = false;
  }
}

class Trie {
  constructor() { this.root = new TrieNode(); }
  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch);
    }
    node.isEnd = true;
  }
  _traverse(str) {
    let node = this.root;
    for (const ch of str) {
      if (!node.children.has(ch)) return null;
      node = node.children.get(ch);
    }
    return node;
  }
  search(word) {
    const node = this._traverse(word);
    return node !== null && node.isEnd;
  }
  startsWith(prefix) {
    return this._traverse(prefix) !== null;
  }
}

Tradeoff:

Quora-specific tips

Quora's follow-up is always: 'how would you extend this to return the top-3 completions by popularity?' — the answer is storing a count or a max-heap of completions at each node. Have that extension ready before the interview ends.

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

Practice these live with InterviewChamp.AI →