Skip to main content

20. Implement Trie (Prefix Tree)

mediumAsked at ServiceNow

Build a trie data structure supporting insert, search, and prefix-search operations. ServiceNow uses this to assess data-structure design skills — trie-based prefix search is the backbone of their universal search autocomplete that spans incidents, assets, and knowledge articles.

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

Source citations

Public interview reports confirming this problem appears in ServiceNow loops.

  • LeetCode Discuss (2026)— Reported as a ServiceNow SDE-II design question in onsite coding rounds.
  • Glassdoor (2025)— Appears in ServiceNow product engineer interviews as a system-design warm-up.

Problem

Implement the Trie class with three operations: insert(word) inserts the string word; search(word) returns true if the exact word is in the trie; startsWith(prefix) returns true if there is any word in the trie 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 will be made to insert, search, and startsWith.

Examples

Example 1

Input
insert('apple'), search('apple'), search('app'), startsWith('app'), insert('app'), search('app')
Output
[null, true, false, true, null, true]

Explanation: After inserting 'apple', 'app' is a prefix but not a full word until explicitly inserted.

Approaches

1. Hash map of full words

Store all inserted words in a Set; search checks membership, startsWith iterates the set for any word beginning with the prefix.

Time
O(n) for startsWith
Space
O(total chars)
class Trie {
  constructor() { this.words = new Set(); }
  insert(word) { this.words.add(word); }
  search(word) { return this.words.has(word); }
  startsWith(prefix) {
    for (const w of this.words) if (w.startsWith(prefix)) return true;
    return false;
  }
}

Tradeoff: startsWith is O(n * L) — unacceptable for 30,000 calls. Does not demonstrate trie knowledge.

2. Trie node with children map and isEnd flag

Each node stores a children map (char -> TrieNode) and an isEnd boolean. Insert walks the trie, creating nodes as needed, and sets isEnd at the last character. Search and startsWith share a traverse helper that returns the terminal node (or null).

Time
O(L) per operation
Space
O(total chars * alphabet)
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;
  }

  _traverse(str) {
    let node = this.root;
    for (const ch of str) {
      if (!node.children.has(ch)) return null;
      node = node.children.get(ch);
    }
    return node;
  }

  search(word) {
    const node = this._traverse(word);
    return node !== null && node.isEnd;
  }

  startsWith(prefix) {
    return this._traverse(prefix) !== null;
  }
}

Tradeoff: O(L) for all operations — optimal. The shared _traverse helper eliminates duplication and makes the distinction between search (requires isEnd) and startsWith (any terminal node) crystal clear.

ServiceNow-specific tips

ServiceNow interviewers specifically test the search vs. startsWith distinction — search requires isEnd=true, while startsWith only needs the node to exist. Candidates who conflate these two fail the design. Bonus signal: mention that ServiceNow's universal search uses a trie variant with relevance scores stored at each node, enabling autocomplete ranked by usage frequency.

Common mistakes

  • search returning true for a prefix that is not a complete word — forgetting to check isEnd.
  • startsWith returning false when the prefix is a complete word but no continuation exists — the node exists and should return true.
  • Using an array of 26 slots instead of a Map for children — fine for ASCII lowercase but brittle; a Map generalizes to Unicode without code changes.

Follow-up questions

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

  • Add a delete(word) operation that removes a word without breaking prefix paths shared by other words.
  • Word Search II (LC 212): find all words in a board that exist in a trie.
  • Design a search autocomplete system ranked by historical query frequency (LC 642).

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 I use an array of 26 slots vs a Map for children?

Array[26] has O(1) indexed access and lower overhead for pure ASCII lowercase inputs. A Map handles Unicode, mixed case, or non-letter characters and avoids allocating 26 slots when most are empty. At ServiceNow, where search spans asset names and incident codes with symbols, a Map is more robust.

How do I delete a word from the trie without breaking other words?

Walk to the terminal node; set isEnd = false. Then backtrack, deleting nodes bottom-up only if they have no children and isEnd is false — this ensures shared prefix paths for other words are preserved.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →