Skip to main content

17. Implement Trie (Prefix Tree)

mediumAsked at Chegg

Build a trie supporting insert, search, and startsWith — directly maps to Chegg's search autocomplete and prefix-based textbook lookup features.

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

Problem

Implement the Trie class with insert(word), search(word) returning true if word is in the trie, and startsWith(prefix) returning true if any previously inserted word has the given prefix.

Constraints

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

Examples

Example 1

Input
Trie trie = new Trie(); trie.insert("apple"); trie.search("apple");
Output
true

Example 2

Input
trie.search("app"); trie.startsWith("app");
Output
false, true

Approaches

1. Hash map children

Each node stores a children map and isEnd flag; operations walk the map character by character.

Time
O(m) per op
Space
O(m*n)
class TrieNode {
  constructor() { this.children = {}; this.isEnd = false; }
}
class Trie {
  constructor() { this.root = new TrieNode(); }
  insert(word) {
    let node = this.root;
    for (const c of word) {
      if (!node.children[c]) node.children[c] = new TrieNode();
      node = node.children[c];
    }
    node.isEnd = true;
  }
}

Tradeoff:

2. Array-indexed children (optimal for lowercase alpha)

Use a fixed 26-slot array instead of a hash map — O(1) child lookup with lower constant overhead for alphabet-only inputs like search queries.

Time
O(m) per op
Space
O(26*m*n) worst-case but cache-friendly
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;
  }
  search(word) {
    let node = this.root;
    for (const c of word) {
      const i = this._idx(c);
      if (!node.children[i]) return false;
      node = node.children[i];
    }
    return node.isEnd;
  }
  startsWith(prefix) {
    let node = this.root;
    for (const c of prefix) {
      const i = this._idx(c);
      if (!node.children[i]) return false;
      node = node.children[i];
    }
    return true;
  }
}

Tradeoff:

Chegg-specific tips

Chegg's search indexing relies heavily on prefix lookups — interviewers will ask how you'd extend this trie to support ranked autocomplete suggestions for textbook titles.

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

Practice these live with InterviewChamp.AI →