73. Implement Trie (Prefix Tree)

Q: Object vs. fixed array for children?

Object is more memory-efficient for sparse alphabets; fixed-26 array is faster for dense use.

Q: How would delete work?

Walk to the terminal, unset isEnd. If no children, also remove from parent (recursively up).

mediumAsked at Reddit

Implement a trie supporting insert, search, and startsWith. Reddit uses this to test prefix-tree design — the same data structure they use in their autocomplete service for subreddit and username completion.

By Sam K., Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Reddit loops.

Glassdoor (2026-Q1)— Reddit search-team on-site canonical.
Blind (2025-12)— Reported on Reddit search and autocomplete rounds.

Problem

A trie 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(), insert(word), search(word), startsWith(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","search","search","startsWith","insert","search"] [[],["apple"],["apple"],["app"],["app"],["app"],["app"]]

Output

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

Approaches

1. Hash set of words

Store all words in a Set. search trivial; startsWith scans all words.

Time: search O(1), startsWith O(n*L)
Space: O(n*L)

// Anti-pattern: startsWith is linear in word count.

Tradeoff: Fails for many prefix queries.

2. Trie tree (optimal)

Each node has 26 children + an isEnd flag. Walk char-by-char.

Time: O(L) per op
Space: O(N*L)

class Trie {
  constructor() {
    this.root = {};
  }
  insert(word) {
    let node = this.root;
    for (const c of word) {
      if (!node[c]) node[c] = {};
      node = node[c];
    }
    node.isEnd = true;
  }
  search(word) {
    const node = this._find(word);
    return !!node && !!node.isEnd;
  }
  startsWith(prefix) {
    return !!this._find(prefix);
  }
  _find(s) {
    let node = this.root;
    for (const c of s) {
      if (!node[c]) return null;
      node = node[c];
    }
    return node;
  }
}

Tradeoff: O(L) per op. Memory scales with total characters in dictionary.

Reddit-specific tips

Reddit interviewers want the standard children-map node. Bonus signal: discuss memory optimization (use an array of 26 vs. an object) and connect to their autocomplete service.

Common mistakes

Marking every node along the path as isEnd (only the terminal one).
Conflating search and startsWith (search requires isEnd).
Allocating a 26-slot array per node when the alphabet is small (memory hog).

Follow-up questions

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

Design Add and Search Words (LC 211) — with wildcards.
Word Search II (LC 212) — Trie + DFS.
Longest word in dictionary (LC 720).

Solve it now

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