208. Implement Trie (Prefix Tree)

Q: When would you use a Map over an array for children?

When the alphabet is large (Unicode), sparse (most keys don't exist), or variable (mix of letters and digits). The array approach is faster in tight loops over a known 26-letter alphabet.

Q: What is the space complexity of a Trie vs. a hash set?

A hash set stores full strings — O(total characters). A Trie stores each unique prefix once — O(total unique characters across all words). For words with long common prefixes, the Trie wins significantly on space.

mediumAsked at Glean

Glean is an enterprise search company — Tries are the backbone of autocomplete and prefix-lookup in their search bar. Expect this to come up and expect deep follow-up questions about real-world trie extensions.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-22

Source citations

Public interview reports confirming this problem appears in Glean loops.

Glassdoor (2026-Q1)— Glean engineers cite Trie implementation as the single most thematically relevant problem given their autocomplete infrastructure.
Blind (2025-12)— Multiple Glean threads report Trie as a guaranteed topic in onsites — candidates are expected to implement and extend it.

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. There are various applications of this data structure, such as autocomplete and spell checking. Implement the Trie class: Trie() initializes the trie object. void insert(word) inserts the string word into the trie. boolean search(word) returns true if word is in the trie (it was inserted before), and false otherwise. boolean startsWith(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

Trie(); insert('apple'); search('apple'); search('app'); startsWith('app'); insert('app'); search('app')

Output

[null,null,true,false,true,null,true]

Explanation: 'apple' is inserted. search('apple') = true. search('app') = false (app was not inserted yet). startsWith('app') = true. After inserting 'app', search('app') = true.

Approaches

1. Array-indexed children (26 children per node)

Each TrieNode holds an array of 26 child pointers (one per lowercase letter) and a boolean isEnd flag. Insert/search/startsWith all walk the same character-by-character path.

Time: O(m) per operation where m = word length
Space: O(ALPHABET_SIZE * m * n) total

class TrieNode {
  constructor() {
    this.children = new Array(26).fill(null);
    this.isEnd = false;
  }
}
class Trie {
  constructor() { this.root = new TrieNode(); }
  _charIndex(ch) { return ch.charCodeAt(0) - 97; }
  insert(word) {
    let node = this.root;
    for (const ch of word) {
      const i = this._charIndex(ch);
      if (!node.children[i]) node.children[i] = new TrieNode();
      node = node.children[i];
    }
    node.isEnd = true;
  }
  search(word) {
    let node = this.root;
    for (const ch of word) {
      const i = this._charIndex(ch);
      if (!node.children[i]) return false;
      node = node.children[i];
    }
    return node.isEnd;
  }
  startsWith(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      const i = this._charIndex(ch);
      if (!node.children[i]) return false;
      node = node.children[i];
    }
    return true;
  }
}

Tradeoff: O(m) per operation. The array-based approach is fast (array index vs. hash) but uses O(26 * nodes) memory. Best for a known, small alphabet like lowercase English letters.

2. Map-indexed children (arbitrary alphabet)

Replace the 26-element array with a Map at each node. This supports any character set (Unicode, digits, symbols) with no wasted null slots.

Time: O(m) per operation
Space: O(m * n) total — only actual children are stored

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) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) return false;
      node = node.children.get(ch);
    }
    return node.isEnd;
  }
  startsWith(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children.has(ch)) return false;
      node = node.children.get(ch);
    }
    return true;
  }
}

Tradeoff: More memory-efficient for sparse tries (few words, long common prefixes). Better for enterprise search where keys include numbers, spaces, or Unicode. Slight constant overhead vs. array indexing.

Glean-specific tips

This is the highest-signal problem in a Glean interview. Before coding, mention the real-world context: 'A Trie is what powers the autocomplete in Glean's search bar — O(prefix length) lookup regardless of how many documents are indexed.' Implement both insert and search cleanly, then proactively explain how startsWith differs from search (no isEnd check). Expect follow-ups: add a 'delete' method, return all words with a given prefix, or rank results by frequency.

Common mistakes

Confusing search and startsWith — search requires isEnd = true at the final node; startsWith only requires reaching the final node.
Not allocating a new TrieNode when an edge doesn't exist — always check and create before descending.
Using node.children[ch] with string keys on a plain object — prototype pollution edge cases exist; use a Map or the 26-array approach.
Forgetting to set isEnd = true after inserting — the word exists in the trie structurally but search() returns false.

Follow-up questions

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

Design Search Autocomplete System (LC 642) — extend Trie with frequency-ranked prefix suggestions.
Add a delete(word) method — decrement reference counts or mark isEnd = false and prune unused nodes.
Replace Words (LC 648) — given a dictionary of roots, replace words in a sentence with their shortest root using a Trie.

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 would you use a Map over an array for children?

When the alphabet is large (Unicode), sparse (most keys don't exist), or variable (mix of letters and digits). The array approach is faster in tight loops over a known 26-letter alphabet.

What is the space complexity of a Trie vs. a hash set?

A hash set stores full strings — O(total characters). A Trie stores each unique prefix once — O(total unique characters across all words). For words with long common prefixes, the Trie wins significantly on space.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →