Problem Statement

Implement Trie (Prefix Tree)

A trie (say it like "try"), also called a prefix tree, is a tree built out of letters. Picture a road map of words. You start at one spot, and every word you store branches off letter by letter. Words that begin the same way share the same road for as long as they match, then split apart. For example, "apple" and "app" travel together down a-p-p, and only after that does "apple" keep going with l-e. We need to build a Trie class with four methods: Trie() sets up an empty trie. insert(word) stores a word. search(word) returns true if that exact word was stored before, and false otherwise. startsWith(prefix) returns true if any stored word begins with that prefix, and false otherwise. This is the same idea behind autocomplete, spell checkers, and phone contact search, because following letters one at a time makes finding words and prefixes fast.

mediumTrieTrieTime: O(m) · Space: O(m)

Signals to notice

implement prefix treestore and search strings by prefixcharacter-by-character tree

Brute force first

Store strings in a list, linear scan for search and prefix — per operation. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.

The key insight

Trie: each node has up to 26 children (one per letter). Insert by walking/creating nodes per character. Search by walking nodes — if you reach the end with isEnd=true, the word exists. per operation where m = word length. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.

Trace it on `ops=["insert","search","search","startsWith","insert","search"], args=["apple","apple","app","app","app","app"]`

insert("apple"): walk root, create a-p-p-l-e nodes; mark e.endOfWord=true
search("apple"): walk a-p-p-l-e all exist; reach e, endOfWord=true -> return true
search("app"): walk a-p-p all exist; reach 2nd p, endOfWord=false -> return false
startsWith("app"): walk a-p-p all exist; reached end of prefix -> return true
insert("app"): walk existing a-p-p nodes; mark 2nd p.endOfWord=true
search("app"): walk a-p-p; reach 2nd p, now endOfWord=true -> return true
returned: [true, false, true, true]

What must stay true

Each path from root to a marked node represents a stored word. Shared prefixes share nodes — 'apple' and 'app' share the first 3 nodes. This is what makes prefix operations instead of scanning all words. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.

Shape of the loop

cur = root
for c in word:                 # insert
    cur.children[c] ||= new TrieNode()
    cur = cur.children[c]
cur.endOfWord = true            # search/startsWith: walk same way,
                                # return false if c missing; else endOfWord / true

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Forgetting to mark terminal nodes — without isEnd, you can't distinguish 'app' (a complete word) from the prefix of 'apple'. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.

Trie Pattern