Skip to main content

16. Implement Trie (Prefix Tree)

mediumAsked at Byju's

Build a Trie supporting insert, search, and startsWith on lowercase strings.

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

Problem

Implement the Trie class with insert(word), search(word), and startsWith(prefix). All input strings are lowercase English letters. Search returns true only on exact words inserted earlier; startsWith returns true when any inserted word has the given prefix.

Constraints

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

Examples

Example 1

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

Example 2

Input
insert('cat'), startsWith('ca'), search('ca')
Output
true, false

Approaches

1. Sorted-list scan

Maintain a sorted array of inserted words and binary-search by prefix.

Time
O(log n) per call
Space
O(total chars)
class Trie{ constructor(){this.a=[];}
  insert(w){const i=this.a.findIndex(x=>x>=w); if(i<0) this.a.push(w); else if(this.a[i]!==w) this.a.splice(i,0,w);} 
  search(w){return this.a.includes(w);} 
  startsWith(p){return this.a.some(w=>w.startsWith(p));} 
}

Tradeoff:

2. Node-per-char trie

Each node holds a children map plus an isEnd flag. Insert/search/startsWith descend one node per character.

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

Tradeoff:

Byju's-specific tips

Byju's recommendation pipelines index lesson titles in tries for autocomplete, so connect your design to learner-search UX during the walk-through.

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

Practice these live with InterviewChamp.AI →