Skip to main content

17. Implement Trie (Prefix Tree)

mediumAsked at GitHub

Build a trie supporting insert, search, and startsWith — the data structure behind GitHub's code search autocomplete and repository name prefix matching.

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

Problem

Implement the Trie class with insert(word), search(word) returning true if the word is in the trie, and startsWith(prefix) returning true if any previously inserted word starts with the prefix.

Constraints

  • 1 <= word.length, prefix.length <= 2000
  • word and prefix consist only of lowercase English letters
  • At most 3×10^4 calls total

Examples

Example 1

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

Example 2

Input
insert('app'); search('app')
Output
true

Approaches

1. Store all words in a Set/Array

Keep a flat list of inserted words; search and prefix check scan the list linearly.

Time
O(n*L) per query
Space
O(n*L)
// words = []; search = words.includes(w); startsWith = words.some(w=>w.startsWith(p))
// Correct but O(n*L) per query — won't scale

Tradeoff:

2. Trie with child-map nodes

Each node holds a children map and an isEnd flag. Insert walks/creates nodes per character; search walks and checks isEnd; startsWith walks and returns whether path exists.

Time
O(L) per operation
Space
O(total chars)
class TrieNode {
  constructor() { this.children = {}; this.isEnd = false; }
}
class Trie {
  constructor() { this.root = new TrieNode(); }
  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) node.children[ch] = new TrieNode();
      node = node.children[ch];
    }
    node.isEnd = true;
  }
  _walk(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children[ch]) return null;
      node = node.children[ch];
    }
    return node;
  }
  search(word) { const n = this._walk(word); return n !== null && n.isEnd; }
  startsWith(prefix) { return this._walk(prefix) !== null; }
}

Tradeoff:

GitHub-specific tips

GitHub code search and repository autocomplete use trie-like inverted indexes; mention how you'd extend isEnd to store metadata (file paths, line numbers) for richer search results.

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 GitHub interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →