Skip to main content

30. Implement Trie (Prefix Tree)

mediumAsked at Postman

Implement a trie supporting insert, search, and prefix-search in O(L).

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

Problem

Implement a Trie (prefix tree) with insert(word), search(word) returning whether the word is in the trie, and startsWith(prefix) returning whether any inserted word has that prefix.

Constraints

  • 1 <= word.length, prefix.length <= 2000
  • Lowercase English letters only
  • Up to 3 * 10^4 calls

Examples

Example 1

Input
insert("apple"); search("apple")
Output
true

Example 2

Input
insert("apple"); search("app"); startsWith("app")
Output
false, true

Approaches

1. Set of words

Store every word in a Set; prefix search loops over all words.

Time
O(n*L) for prefix
Space
O(total chars)
// startsWith(p) = [...set].some(w => w.startsWith(p)) — linear

Tradeoff:

2. Linked node trie

Each node holds a Map<char, child> and an isEnd flag. Insert walks/creates children; search walks and checks isEnd; startsWith walks only.

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

Tradeoff:

Postman-specific tips

Postman ships a prefix-search trie in the URL-bar autocomplete for known endpoints — the linked-node form is exactly what they have in production, so know it cold.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →