Skip to main content

208. Implement Trie (Prefix Tree)

mediumAsked at LinkedIn

Implement a Trie with insert, search, and startsWith. LinkedIn asks this because it's the foundation of their typeahead and autocomplete features — they want a clean node-with-children-map structure and the isEnd boolean.

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

Source citations

Public interview reports confirming this problem appears in LinkedIn loops.

  • Glassdoor (2026-Q1)— LinkedIn SWE onsite reports list Trie implementation as a 30-minute warm-up before an autocomplete or word-search follow-up.
  • Blind (2025-12)— LinkedIn writeups specifically tie this to their typeahead/autocomplete use cases as the why-this-question signal.

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 in total 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]

Approaches

1. Hash map of children + isEnd boolean (canonical)

Each node has a Map of char to child node and a boolean isEnd. Insert walks/creates nodes per char and sets isEnd at the leaf. Search walks; returns true only if reached and isEnd. startsWith walks; returns true if reached (no isEnd check).

Time
O(L) per operation where L is word length
Space
O(total characters across all inserts)
class Trie {
  constructor() { this.root = { children: new Map(), isEnd: false }; }
  insert(word) {
    let node = this.root;
    for (const c of word) {
      if (!node.children.has(c)) node.children.set(c, { children: new Map(), isEnd: false });
      node = node.children.get(c);
    }
    node.isEnd = true;
  }
  search(word) {
    const node = this._walk(word);
    return node !== null && node.isEnd;
  }
  startsWith(prefix) {
    return this._walk(prefix) !== null;
  }
  _walk(str) {
    let node = this.root;
    for (const c of str) {
      if (!node.children.has(c)) return null;
      node = node.children.get(c);
    }
    return node;
  }
}

Tradeoff: Map-based — handles arbitrary character sets. The shared _walk helper avoids duplicating the traversal logic between search and startsWith.

2. Array-of-26 children (lowercase optimization)

Replace the Map with a 26-slot array indexed by char - 'a'. Faster constant-factor but only works for lowercase a-z.

Time
O(L)
Space
O(26 * nodes)
class TrieArray {
  constructor() { this.root = { children: new Array(26).fill(null), isEnd: false }; }
  insert(word) {
    let node = this.root;
    for (const c of word) {
      const i = c.charCodeAt(0) - 97;
      if (!node.children[i]) node.children[i] = { children: new Array(26).fill(null), isEnd: false };
      node = node.children[i];
    }
    node.isEnd = true;
  }
  search(word) {
    const node = this._walk(word);
    return node !== null && node.isEnd;
  }
  startsWith(prefix) { return this._walk(prefix) !== null; }
  _walk(str) {
    let node = this.root;
    for (const c of str) {
      const i = c.charCodeAt(0) - 97;
      if (!node.children[i]) return null;
      node = node.children[i];
    }
    return node;
  }
}

Tradeoff: Faster array access vs Map hash. Uses 26 * 8 = 208 bytes per node (sparse). Worth it for high-throughput typeahead workloads; otherwise Map is cleaner.

LinkedIn-specific tips

LinkedIn interviewers grade two specific things: (1) Do you separate search vs startsWith correctly? Search must also check isEnd; startsWith does not. (2) Do you spot the shared _walk helper? It's a 30-second refactor that signals you write maintainable code. Be ready for the follow-up: 'How would you delete a word?' (Recurse to the leaf, unset isEnd, prune empty subtrees on the way up.)

Common mistakes

  • Treating search and startsWith identically — search must require isEnd === true.
  • Initializing isEnd globally in the class instead of per-node — every node would share the same flag.
  • In the array version, forgetting to initialize children as Array(26).fill(null) — gives undefined behavior on unfilled slots.

Follow-up questions

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

  • Add a delete(word) method.
  • Design Add and Search Words Data Structure (LC 211) — wildcard '.' support.
  • Word Search II (LC 212) — use a Trie to search multiple words in a grid simultaneously.

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

Array (size 26 or 256) for fixed alphabets — faster constant factor. Map for arbitrary or Unicode chars — flexible but slower per-access. For LinkedIn's typeahead workload, the array version typically wins.

Why is isEnd needed?

Because 'app' and 'apple' share a prefix; without isEnd you can't distinguish 'app was inserted' from 'app is just a prefix of apple.' isEnd marks where actual words end.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →