Foundations

Core idea: A trie turns a set of words into a tree of characters. Walking one edge per letter, every word becomes a path from the root, and words that share a prefix share that prefix's path. A single boolean flag (is_end) on a node says "a word ends right here." That layout makes "does any word start with app?" cost only the length of app — never the size of the dictionary.

Problem, rephrased

You're building the in-memory index behind a search box. Words stream in one at a time (insert), and the box must answer two very different questions instantly:

• Exact lookup — "is apple a word I've stored?" (search)
• Prefix lookup — "is there any stored word that begins with app?" (startsWith)

Build a structure Trie supporting:

• insert(word) — add word to the index.
• search(word) — return True only if the exact word was inserted earlier.
• startsWith(prefix) — return True if some stored word has prefix as a leading substring (the prefix itself need not be a stored word).

This is LeetCode 208. Inputs are non-empty strings of lowercase letters a–z.

Here's a transcript on a fresh trie, top to bottom:

The crux is row 3 vs. row 6: the path app existed all along, but it only counts as a stored word once is_end is set on its final node. That distinction — path exists vs. word ends here — is the whole trie in one sentence.