Skip to main content

208. Implement Trie (Prefix Tree)

mediumAsked at Amazon

Implement a Trie with insert, search, and startsWith operations. Amazon asks this to test whether you can implement the canonical multi-way tree data structure with the 'children map + isEnd flag' pattern.

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

Source citations

Public interview reports confirming this problem appears in Amazon loops.

  • Glassdoor (2026-Q1)— Amazon SDE I/II onsite reports cite this as the trie-data-structure round.
  • Blind (2025-12)— Recurring Amazon interview problem.

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: insert(String word) inserts the string word into the trie, search(String word) returns true if word is in the trie, startsWith(String prefix) returns true if there is a previously inserted word with 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
Trie(); insert('apple'); search('apple'); search('app'); startsWith('app'); insert('app'); search('app')
Output
[null,null,true,false,true,null,true]

Approaches

1. Trie node with children map + isEnd flag (optimal)

Each node stores: children (Map of char -> child node) + isEnd (boolean). Insert walks/creates path; search walks path and checks isEnd; startsWith walks path and returns true.

Time
O(L) per operation
Space
O(N * L) total
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;
  }
  _walk(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children.has(ch)) return null;
      node = node.children.get(ch);
    }
    return node;
  }
  search(word) {
    const node = this._walk(word);
    return !!node && node.isEnd;
  }
  startsWith(prefix) {
    return this._walk(prefix) !== null;
  }
}

Tradeoff: Map-based children scales to any alphabet. The isEnd flag distinguishes 'word ends here' from 'merely a prefix.' search and startsWith differ only in the final check.

2. Trie node with fixed-size array (alternative)

Use an array of 26 child pointers indexed by (char - 'a'). Faster lookup; only works for lowercase English.

Time
O(L) per operation
Space
O(N * L * 26)
class TrieNodeArr {
  constructor() {
    this.children = new Array(26).fill(null);
    this.isEnd = false;
  }
}

class TrieArr {
  constructor() {
    this.root = new TrieNodeArr();
  }
  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 TrieNodeArr();
      node = node.children[idx];
    }
    node.isEnd = true;
  }
  _walk(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      const idx = ch.charCodeAt(0) - 97;
      if (!node.children[idx]) return null;
      node = node.children[idx];
    }
    return node;
  }
  search(word) {
    const node = this._walk(word);
    return !!node && node.isEnd;
  }
  startsWith(prefix) {
    return this._walk(prefix) !== null;
  }
}

Tradeoff: Faster constant factor than Map. Wastes space on sparse tries because every node allocates 26 slots.

Amazon-specific tips

Amazon interviewers grade this on whether you understand the role of isEnd. State out loud: 'Without isEnd, search and startsWith would be identical. The flag distinguishes a complete word from a prefix path.' This articulation is what separates 'I implemented a trie' from 'I understand a trie.'

Common mistakes

  • Confusing search and startsWith — they differ ONLY in the final isEnd check.
  • Forgetting to set isEnd on insert.
  • Allocating 26 children per node when the input alphabet is small (overkill on memory).

Follow-up questions

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

  • Add and Search Word (LC 211) — '.' wildcard.
  • Word Search II (LC 212) — trie + board DFS.
  • Implement a Trie with delete operation.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Map or array — which does Amazon prefer?

Both are accepted. Array is faster on lowercase English; Map is more flexible. Lead with whichever you can code without bugs.

What's the most-common bug?

Skipping isEnd and treating search and startsWith as identical. The interviewer will check whether you handle 'app' being a stored word vs just a prefix of 'apple.'

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →