A tree of letters that makes “does any word start with this?” very fast.
The idea (phone auto-complete)
When you type “ca” and your phone suggests “cat”, “car” and “cart”, something has to find every word that starts with “ca” without scanning the whole dictionary. A trie stores words as paths of letters from a single root. Words that start the same way share the same beginning of the path.
Insert a word: walk down, one letter per step. If the edge for that letter does not exist, create it. Mark the last node as “a word ends here” (drawn as a double circle).
Search a word: walk down its letters. Missing edge → not there. If you arrive, the word exists only if the last node is marked as a word end.
StartsWith a prefix: the same walk, but arriving at all is enough.
Notice: car is a prefix of cart. Both can be words, so “word end” is a separate mark, not the same as “has no children”.
Watch it work
Try it
Insert cat, car, cart. How many nodes does the tree have versus the 10 letters you typed? That saving is the point.
Run search ca and then prefix ca. Why do the answers differ?
Query search dot when do and dog exist. Where does the walk stop?
Insert two completely different words, like apple, zebra. Do they share anything?
Common mistakes
Forgetting the word-end flag. Without it, Search("ca") would wrongly say yes once “cat” is stored.
Not initializing the children map. Writing to a nil map panics in Go, so create map[rune]*Trie{} for every new node.
Mixing up Search and StartsWith. Search needs the end flag; StartsWith does not.
Memory. Every node holds a map. For only lowercase letters, a [26]*Trie array is faster and often smaller.
Complexity, in plain English: insert, search and prefix checks all cost one step per letter of the word, no matter how many words are stored (O(L) for a word of length L). The price is memory: up to one node per stored letter.