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 Sam K., Founder, InterviewChamp.AI · Last verified 2026-05-19

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.