Skip to main content

208. Implement Trie (Prefix Tree)

mediumAsked at Elastic

Build a prefix tree supporting insert, search, and startsWith. Tries are the foundational data structure behind Elasticsearch's prefix query, completion suggester, and edge-n-gram token filter — implementing one from scratch is one of the most domain-relevant questions Elastic asks.

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

Source citations

Public interview reports confirming this problem appears in Elastic loops.

  • Glassdoor (2026-Q1)— Trie implementation and prefix-search problems are consistently flagged as high-priority questions in Elastic SWE onsite reports.
  • Blind (2025-12)— Multiple Elastic interview threads identify Implement Trie as a must-prepare question given Elasticsearch's completion suggester and autocomplete features.

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 the string word is in the trie (i.e., was inserted before), and false otherwise. boolean startsWith(String prefix) returns true if there is a previously inserted string that has the prefix prefix, and false otherwise.

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]

Explanation: search('app') is false until 'app' is explicitly inserted. startsWith('app') is true because 'apple' starts with 'app'.

Approaches

1. Array-children Trie node (26 fixed slots)

Each node has an array of 26 child pointers (one per lowercase letter) and a boolean isEnd flag. Insert walks the trie, creating nodes as needed. Search and startsWith traverse existing nodes.

Time
O(m) per operation where m = key length
Space
O(m * alphabet_size) worst case
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(str) {
    let node = this.root;
    for (const ch of str) {
      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: O(m) time per operation — optimal. Each node uses 26 slots regardless of how many children exist, so space can be high for sparse tries.

2. Map-children Trie node (sparse, general alphabet)

Replace the fixed 26-slot array with a Map from character to child node. More memory-efficient for sparse tries and works for any alphabet.

Time
O(m)
Space
O(total characters inserted)
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 n = this._traverse(word); return n !== null && n.isEnd; }
  startsWith(prefix) { return this._traverse(prefix) !== null; }
}

Tradeoff: Same O(m) time, but uses only as much space as characters actually inserted. Preferred for large or multi-language vocabularies — more representative of real search-engine tries.

Elastic-specific tips

Elastic interviewers will ask how this relates to their search product. Be prepared to say: 'Elasticsearch's completion suggester is built on a finite-state transducer, which is a space-compressed Trie. The prefix query uses a similar prefix-scan pattern. The edge-n-gram token filter generates all prefixes of each token at index time — effectively pre-building a Trie in the inverted index.' This depth of domain connection is what separates strong Elastic candidates.

Common mistakes

  • Forgetting the isEnd flag — search() and startsWith() are different operations; only search() requires isEnd = true at the target node.
  • Using ch - 'a' without the charCodeAt conversion in JavaScript — JS doesn't support char arithmetic directly.
  • Returning true from startsWith when the traversal reaches null — null means the prefix doesn't exist.
  • Not creating a new root in the constructor — all operations depend on this.root being a valid TrieNode.

Follow-up questions

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

  • Design Search Autocomplete System (LC 642) — extends Trie with frequency ranking and top-K suggestions.
  • Word Search II (LC 212) — use a Trie to accelerate searching for all words in a 2D board.
  • How would you implement a compressed Trie (Patricia/Radix tree) to reduce node count for common prefixes?

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 should I use array-children vs. Map-children?

Array-children has better cache performance for dense alphabets (e.g., lowercase English only). Map-children is better for sparse vocabularies or multi-byte character sets — closer to how production search engines store tries.

What is the difference between search and startsWith?

search requires the traversal to end at a node with isEnd = true. startsWith only requires a non-null node at the end of the prefix — the word need not be complete.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →