Skip to main content

208. Implement Trie (Prefix Tree)

mediumAsked at Microsoft

Implement Trie is the Microsoft data-structure design medium. The clean answer is a node class with a children object and an isEnd flag. Microsoft cares that you can write insert, search, and startsWith without mixing them up — they share traversal logic but stop on different conditions.

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

Source citations

Public interview reports confirming this problem appears in Microsoft loops.

  • Glassdoor (2026-Q1)— Microsoft Azure/Office org onsite reports list Implement Trie as a recurring 30-minute data-structure-design medium.
  • Blind (2025-12)— Microsoft L60/L61 reports include Implement Trie as a recurring topic, often as a prelude to Word Search II.

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 spellchecker. 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 word 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 will be made to insert, search, and startsWith.

Examples

Example 1

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

Explanation: Insert 'apple'. Search 'apple' returns true. Search 'app' returns false (not yet inserted as a word). startsWith 'app' returns true. Insert 'app'. Search 'app' returns true.

Approaches

1. Node class with children map + isEnd flag (optimal)

Each node holds a children object keyed by char and a boolean isEnd. Insert walks/creates the path and marks the last node. Search walks and checks isEnd at the end. startsWith walks and returns true regardless of isEnd.

Time
O(m) per operation where m is word length
Space
O(total chars inserted)
class TrieNode {
  constructor() {
    this.children = {};
    this.isEnd = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }
  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) node.children[ch] = new TrieNode();
      node = node.children[ch];
    }
    node.isEnd = true;
  }
  _walk(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) return null;
      node = node.children[ch];
    }
    return node;
  }
  search(word) {
    const node = this._walk(word);
    return node !== null && node.isEnd;
  }
  startsWith(prefix) {
    return this._walk(prefix) !== null;
  }
}

Tradeoff: Linear time per operation in the word length. The shared _walk helper makes search and startsWith correct-by-construction — the only difference is whether you require isEnd. Forgetting the isEnd check is the most common bug; the helper prevents it.

2. Fixed 26-slot array per node

Same shape but children is a 26-length array indexed by ch.charCodeAt(0) - 97.

Time
O(m)
Space
O(26 * total nodes)
class TrieNode {
  constructor() {
    this.children = new Array(26).fill(null);
    this.isEnd = false;
  }
}

Tradeoff: Slightly faster in practice (no hash overhead) but more memory per node, and only works if the alphabet is fixed. Microsoft will accept either; the object/map version is preferred for clarity unless they ask 'how would you reduce memory?'

Microsoft-specific tips

Microsoft is grading whether you can SEPARATE the three operations cleanly. Before writing code, narrate the difference: 'search needs the path to exist AND the last node to be marked end-of-word. startsWith only needs the path to exist.' That two-sentence framing is what catches the candidates who silently merge the two and ship a broken search.

Common mistakes

  • Returning true for search without checking isEnd — passes startsWith semantics but fails search.
  • Forgetting to mark isEnd in insert — every search returns false.
  • Mixing children as both an object and an array across operations.

Follow-up questions

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

  • Word Search II (LC 212) — build a trie of words, DFS the grid against the trie.
  • Add and Search Word (LC 211) — add wildcard '.' that matches any single char.
  • Replace Words (LC 648) — root-prefix replacement 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

Why a separate isEnd flag and not just check if children is empty?

Because 'app' and 'apple' coexist: 'app' is an end-of-word but its node still has children. Empty-children would wrongly reject 'app' once 'apple' is added.

Object map or array of 26?

Object map is more readable and handles any alphabet. The 26-array is a micro-optimization Microsoft mentions if they ask 'how would you make this faster.'

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →