Skip to main content

208. Implement Trie (Prefix Tree)

mediumAsked at Duolingo

Build a trie that supports insert, search, and prefix-match — the core data structure powering Duolingo's autocomplete, spell-check hints, and word-bank prefix filtering that learners interact with on every vocabulary exercise.

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

Problem

Implement the Trie class with three operations: insert(word) stores a word in the trie; search(word) returns true if the exact word exists; startsWith(prefix) returns true if any previously inserted word begins with 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 will be made to insert, search, and startsWith

Examples

Example 1

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

Explanation: 'app' becomes a valid word only after the second insert.

Approaches

1. Hash map per node

Each node stores a Map of children and a boolean isEnd; all three operations traverse character by character.

Time
O(k) per operation (k = word length)
Space
O(N * k) for all inserted words
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;
  }

  search(word) {
    const node = this._traverse(word);
    return node !== null && node.isEnd;
  }

  startsWith(prefix) {
    return this._traverse(prefix) !== null;
  }

  _traverse(s) {
    let node = this.root;
    for (const ch of s) {
      if (!node.children.has(ch)) return null;
      node = node.children.get(ch);
    }
    return node;
  }
}

Tradeoff:

2. Fixed-size array per node (faster lookup)

Replace the Map with a 26-slot array indexed by character code; same traversal logic but avoids Map hashing overhead.

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

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  _idx(ch) {
    return ch.charCodeAt(0) - 97;
  }

  insert(word) {
    let node = this.root;
    for (const ch of word) {
      const i = this._idx(ch);
      if (!node.children[i]) node.children[i] = new TrieNode();
      node = node.children[i];
    }
    node.isEnd = true;
  }

  search(word) {
    const node = this._traverse(word);
    return node !== null && node.isEnd;
  }

  startsWith(prefix) {
    return this._traverse(prefix) !== null;
  }

  _traverse(s) {
    let node = this.root;
    for (const ch of s) {
      const i = this._idx(ch);
      if (!node.children[i]) return null;
      node = node.children[i];
    }
    return node;
  }
}

Tradeoff:

Duolingo-specific tips

The trie is Duolingo's single most relevant data structure question — autocomplete, spell hint, and word-bank prefix filtering all live on trie queries. Interviewers look for three things: a clean _traverse helper shared by search and startsWith (no copy-paste), the isEnd sentinel to distinguish prefix-only nodes from complete words, and awareness of the Map vs. fixed-array tradeoff. Mention that the 26-slot array wins on lookup speed at the cost of space — in a mobile dictionary with a bounded alphabet that is the right tradeoff.

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

Practice these live with InterviewChamp.AI →