Skip to main content

72. Implement Trie (Prefix Tree)

mediumAsked at Salesforce

Implement a trie supporting insert, search, and startsWith. Salesforce uses tries in their autocomplete and SOQL keyword lookup.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce autocomplete and SOQL keyword lookup use tries.
  • Blind (2025)— Common Salesforce backend onsite question.

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. 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. boolean startsWith(String prefix) returns true if any previously inserted word has the prefix 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. Map of words (no trie)

Use a Set for search. For startsWith, scan all keys.

Time
O(n) for startsWith
Space
O(total chars)
// Cheat — won't impress Salesforce.

Tradeoff: Defeats the purpose. They want the trie.

2. Trie node with children map and isEnd flag

Each node has children: {char: node} and isEnd: boolean.

Time
O(L) per op where L = word length
Space
O(total chars across words)
class Trie {
  constructor() { this.root = { children: {}, isEnd: false }; }
  insert(word) {
    let node = this.root;
    for (const c of word) {
      if (!node.children[c]) node.children[c] = { children: {}, isEnd: false };
      node = node.children[c];
    }
    node.isEnd = true;
  }
  _walk(prefix) {
    let node = this.root;
    for (const c of prefix) {
      if (!node.children[c]) return null;
      node = node.children[c];
    }
    return node;
  }
  search(word) {
    const n = this._walk(word);
    return n !== null && n.isEnd;
  }
  startsWith(prefix) {
    return this._walk(prefix) !== null;
  }
}

Tradeoff: Canonical trie. Reuses _walk for both search and startsWith. The isEnd flag distinguishes whole words from prefixes.

Salesforce-specific tips

Salesforce uses tries in their autocomplete suggestions and SOQL keyword lookup. They grade on whether you abstract _walk to avoid code duplication between search and startsWith. Bonus signal: discuss the space-efficient compact-trie (Patricia trie) for sparse alphabets.

Common mistakes

  • Conflating search and startsWith — startsWith doesn't require isEnd.
  • Using fixed-size arrays instead of maps — fine for 26 letters but breaks on Unicode.
  • Not setting isEnd at the end of insert — search returns false on inserted words.

Follow-up questions

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

  • Design Add and Search Words Data Structure (LC 211) — supports '.' wildcards.
  • Word Search II (LC 212) — Trie + DFS.
  • Replace Words (LC 648).

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why isEnd?

To distinguish between 'this prefix exists' and 'this whole word was inserted'. Without it, 'app' would search-true after inserting 'apple'.

Array of 26 vs Map?

Array is faster and uses less memory for ASCII lowercase. Map is more flexible (Unicode, sparse). For interviews, Map is cleaner.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →