Skip to main content

72. Implement Trie (Prefix Tree)

mediumAsked at Workday

Implement a trie with insert, search, and startsWith. Workday uses this for prefix-search infrastructure — same data structure powering autocomplete on employee names and department codes.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday autocomplete-team SDE2 onsite.

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(), 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 all words

Store every word; for startsWith, scan all.

Time
search O(1), startsWith O(N * L)
Space
O(N * L)
// Set<string> with prefix scan

Tradeoff: Defeats the point — prefix queries become linear in dataset.

2. Node tree with child map

Each node has children (map or array) and isEnd flag. Walk character-by-character.

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

Tradeoff: Single walker function reused for search and startsWith. Map of children is flexible for any alphabet.

Workday-specific tips

Workday wants you to factor the walking logic into a helper (_walk). search and startsWith differ only in whether they check isEnd. Articulate this DRY principle while coding.

Common mistakes

  • Not setting isEnd on insert — search returns false for inserted words.
  • Conflating search and startsWith — duplicating logic.
  • Using a 26-element array when the alphabet is unknown.

Follow-up questions

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

  • Add and Search Word (LC 211) — wildcards.
  • Word Search II (LC 212) — trie + DFS in grid.
  • Compress with radix trees.

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 26-array?

Array is faster for lowercase-only. Map is more flexible (Unicode, sparse alphabets). For 26 letters, both work.

Why factor _walk?

search and startsWith both walk to a node; they differ only in the final check. DRYing this is a code-quality signal.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →