Trie (Prefix Tree)

Build a Trie class — a character-keyed tree that stores a set of strings and answers two questions about them in time proportional to the length of the query string, not the size of the set. Each path from the root spells out a stored word; each node holds an isEnd flag marking whether the path so far is a complete inserted word or just a prefix on the way to one. Tries are the data structure behind autocomplete, spell-check, and IP-routing tables — anywhere you need "does any of my N stored strings start with this prefix?" without scanning N. See MDN's tree glossary for the broader concept.

Signature

class Trie {
  constructor()                       // empty trie
  insert(word: string): void          // store an exact word
  search(word: string): boolean       // true ONLY if this exact word was inserted
  startsWith(prefix: string): boolean // true if any inserted word starts with this prefix
}

word and prefix are strings. Both can be empty. Character comparison is case-sensitive: 'App' and 'app' are different words.

Examples

const t = new Trie();
t.insert('apple');
t.search('apple');     // true  — exact match
t.search('app');       // false — 'app' was never inserted as a whole word
t.startsWith('app');   // true  — 'apple' starts with 'app'
t.startsWith('apz');   // false — no inserted word starts with 'apz'

const t = new Trie();
t.insert('app');
t.insert('apple');
t.search('app');       // true  — now BOTH are stored words
t.search('apple');     // true
t.startsWith('app');   // true
t.search('apples');    // false — 'apples' is longer than anything inserted

const empty = new Trie();
empty.search('a');         // false — nothing inserted
empty.startsWith('a');     // false
empty.startsWith('');      // false — even the empty prefix has no words to start

const t = new Trie();
t.insert('');
t.search('');              // true  — empty string was inserted
t.startsWith('');          // true  — every word (including '') starts with ''

Notes

• search is exact, startsWith is not — search('app') is true only if 'app' itself was inserted; it is not enough that some longer word like 'apple' happens to pass through that node.
• Empty strings are valid — insert(''), search(''), and startsWith('') must all work. Treat '' like any other word.
• Case-sensitive — 'App' and 'app' are distinct keys. Do not lowercase.
• Inserting the same word twice is idempotent — the trie's behavior should be identical to inserting it once.
• Out of scope — delete(word), listing all words with a given prefix (autocomplete), and Unicode normalization. Just the three methods above.
• Performance bar — insert, search, and startsWith should all run in time proportional to the length of the input string, regardless of how many words are already stored.