Skip to main content

208. Implement Trie (Prefix Tree)

mediumAsked at Twilio

Implement Trie is Twilio's prefix-tree design probe: build a data structure supporting insert, search, and startsWith over lowercase-letter words. The grading rubric weighs whether you choose the 26-slot child array (fast, fixed memory) or a hash-map child structure (memory-frugal for sparse keysets).

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

Source citations

Public interview reports confirming this problem appears in Twilio loops.

  • Glassdoor (2026-Q1)— Cited in Twilio backend SWE on-site rounds for the platform-engineering team.
  • LeetCode Discuss (2025-11)— Listed in Twilio interview reports as the precursor to autocomplete-suggestion design questions.

Problem

A trie (pronounced as 'try') or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. Implement the Trie class: Trie() initializes the trie object; void insert(String word) inserts the string word into the trie; boolean search(String word) returns true if word is in the trie; boolean startsWith(String prefix) returns true if any 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 in total 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]

Approaches

1. HashSet of inserted words (rejected for the prefix contract)

Store every inserted word in a Set; search is membership; startsWith scans every entry.

Time
search O(1), startsWith O(n * L)
Space
O(n * L)
class TrieSet {
  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: Search is fast but startsWith is O(n * L) per call. At 3 * 10^4 calls with L = 2000 that's TLE territory. Twilio rejects this — the whole point is that the prefix tree gives O(L) startsWith.

2. Array-of-26 child nodes (optimal)

Each node has a fixed 26-slot children array (indexed by char - 'a') and an isEnd boolean.

Time
O(L) per op
Space
O(total chars * 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 i = ch.charCodeAt(0) - 97;
      if (!node.children[i]) node.children[i] = new TrieNode();
      node = node.children[i];
    }
    node.isEnd = true;
  }
  _traverse(word) {
    let node = this.root;
    for (const ch of word) {
      const i = ch.charCodeAt(0) - 97;
      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: Constant-time per character because the child lookup is an array index. Memory is O(total chars * 26) — fine for ASCII lowercase but explodes for Unicode. The factored-out _traverse helper deduplicates search and startsWith.

3. Hash-map child nodes (memory-frugal alternative)

Each node has a Map<char, TrieNode> for children — only allocates for characters that exist.

Time
O(L) per op
Space
O(total chars)
class TrieNodeMap {
  constructor() {
    this.children = new Map();
    this.isEnd = false;
  }
}

class TrieMap {
  constructor() { this.root = new TrieNodeMap(); }
  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNodeMap());
      node = node.children.get(ch);
    }
    node.isEnd = true;
  }
  _traverse(word) {
    let node = this.root;
    for (const ch of word) {
      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: Same time but with hash-map constant-factor overhead. Wins on memory when most nodes have few children (the typical real-world case).

Twilio-specific tips

Twilio reviewers explicitly want both approaches discussed. Array-26 wins on raw speed and is the canonical answer for the 26-char ASCII contract; map-of-char wins when the alphabet is large or sparse. Mentioning the autocomplete extension (return the K most-likely completions for a prefix) signals you can extend to LC 642 — that's the on-site follow-up.

Common mistakes

  • Forgetting the isEnd flag — without it, search('app') after only inserting 'apple' returns true, which is wrong.
  • Mutating the root reference instead of walking with a local pointer.
  • Indexing the array with a raw char ('a'.charCodeAt(0) = 97) instead of a char-minus-97 offset — leads to out-of-bounds or wasted slots.

Follow-up questions

An interviewer at Twilio may pivot to one of these next:

  • How would you add a delete(word) operation? (Reverse-walk after a successful search; for each node, drop the child if it has no other children AND isn't an isEnd.)
  • How would you implement WordDictionary with '.' wildcards (LC 211)? (DFS through children on a '.'; otherwise direct lookup.)
  • How would you return the K most-likely completions for a prefix (LC 642)? (Store top-K weighted suggestions at each node, or walk subtree and heap-rank.)

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

When is the array-of-26 layout NOT the right choice?

For large or sparse alphabets — Unicode (10^4+ codepoints) or domain alphabets like file paths. The 26-slot pre-allocation per node burns memory you'll never use.

Is the trie always asymptotically faster than a HashMap for prefix queries?

For startsWith yes — O(L) vs O(n*L) with a Set. For exact search both are O(L) with the trie and O(L) for the Set hash, but Set has a smaller constant. Use a trie specifically when you need prefix queries.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Implement Trie (Prefix Tree) and other Twilio interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →