Skip to main content

79. Implement Trie (Prefix Tree)

mediumAsked at Datadog

Implement a Trie with insert, search, and startsWith. Datadog uses this as the gateway to prefix-search problems — same shape as their tag-name autocomplete that serves their high-cardinality search UI.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — tag-name autocomplete analog.
  • Blind (2025-12)— Recurring Datadog 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. There are various applications of this data structure, such as autocomplete and spellchecker. Implement the Trie class with 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('apple'), search('apple'), search('app'), startsWith('app'), insert('app'), search('app')
Output
[null,null,true,false,true,null,true]

Approaches

1. Hashset of all words

Set for search; substring scan for startsWith.

Time
search O(L), startsWith O(n)
Space
O(total chars)
// Set for search; for startsWith, iterate all words and check startsWith.

Tradeoff: startsWith is O(n) where n = words count. Datadog's autocomplete demands O(L).

2. Trie with children map (optimal)

Each node has a children Map + isEnd flag. Insert walks/creates; search/startsWith walk; search checks isEnd.

Time
O(L) per op
Space
O(total chars)
class Trie {
  constructor() { this.root = { children: new Map(), isEnd: false }; }
  insert(word) {
    let n = this.root;
    for (const c of word) {
      if (!n.children.has(c)) n.children.set(c, { children: new Map(), isEnd: false });
      n = n.children.get(c);
    }
    n.isEnd = true;
  }
  _walk(s) {
    let n = this.root;
    for (const c of s) {
      if (!n.children.has(c)) return null;
      n = n.children.get(c);
    }
    return n;
  }
  search(word) { const n = this._walk(word); return n !== null && n.isEnd; }
  startsWith(prefix) { return this._walk(prefix) !== null; }
}

Tradeoff: All ops are O(L) regardless of total words. Datadog-canonical for prefix queries.

Datadog-specific tips

Datadog will follow up with: 'Now support delete' or 'Now find all words with a prefix.' Show that the trie structure makes both natural — delete by clearing isEnd and pruning empty branches; find-all via DFS from the prefix node.

Common mistakes

  • Using a 26-element array but forgetting to handle non-letter inputs — Map is safer.
  • Forgetting the isEnd flag — can't distinguish 'word ends here' from 'word continues.'
  • Not returning early in _walk when child is missing — null deref.

Follow-up questions

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

  • Word Search II (LC 212) — Trie + DFS on a board.
  • Add and Search Word (LC 211) — Trie + wildcard.
  • Datadog-style: tag-name autocomplete over high-cardinality tag space.

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 vs array for children?

Array (size 26) is faster for ASCII lowercase. Map is more general (Unicode, casing). Datadog accepts either.

Why isEnd separate from children?

A word and its prefix can both be present. 'app' is a word AND a prefix of 'apple'; we need isEnd to distinguish.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →