Implement Trie (Prefix Tree)

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 with insert, search, and startsWith methods.

Examples

The brute-force approach

Store all inserted words in a list. For search, check membership. For startsWith, check any word that starts with prefix.

words = []
insert(word) → words.append(word)
search(word) → word in words
startsWith(prefix) → any(w.startswith(prefix) for w in words)

O(m × n) for search and startsWith where m=word count, n=average length. Trie achieves O(L) for each operation where L is the word/prefix length.

Spotting the pattern

This is a Trie problem. The key question to ask yourself:

What's the difference between search and startsWith in terms of what they check at the end of the traversal?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.