Day 18 — Tries

A hash set can tell you “is this exact word in my collection?” in O(1). But it’s useless the moment you ask “how many of my words start with app?” — there’s no structure connecting apple, application, and apply. A trie (prefix tree) is the data structure that makes prefixes first-class: words that share a beginning share a path.

The name is from retrieval (and it’s pronounced “try”). The idea is simple and visual — every node is a character, every root-to-marked-node path is a word, and shared prefixes are stored exactly once.

A trie holding {cat, car, card, dog, do}

● root  ● end-of-word  ● internal

'cat', 'car', and 'card' all share the path c→a, then branch. 'do' and 'dog' share d→o, and 'do' is itself a word (green) sitting on the path to 'dog'. Common prefixes are stored once — that's the whole trick.

What you’ll learn today

The node anatomy — a children map and a single isEndOfWord flag, and why those two things are the entire data structure
The three core operations — insert, search, and startsWith, each in O(L) where L is the word length (independent of how many words you’ve stored)
Why a trie beats a hash set for prefix work, and the time/space trade-off it makes
Variations — compressed tries (radix trees), the bitwise trie for XOR problems, and ternary search trees
Eight interview problems — Implement Trie, Add & Search Word (wildcards), Word Search II, Replace Words, Map Sum Pairs, Longest Word, Maximum XOR, and Search Suggestions

The trie’s superpower is that lookup cost depends on the word length, not the number of words. Searching for a 5-letter word takes 5 steps whether your trie holds 10 words or 10 million. That’s why autocomplete, spell-checkers, IP routing tables, and dictionary problems all reach for it — the collection can be enormous and queries stay cheap.

Roadmap

Introduction — what a trie is, the node structure, how it stores words, and when it beats a hash map.
Core Operations — insert, search, startsWith with full code in C++/Python/Java and an interactive trie you can break.
Variations & Tricks — compressed/radix tries, the bitwise trie (the key to XOR problems), ternary search trees, and storing values at nodes.
Basic Questions — warm-ups: count words with a prefix, autocomplete, delete a word, longest common prefix.
Practice Questions — eight interview classics, from Implement Trie to Maximum XOR.

Tries are the first of the specialized structures (Phase 6). They feel like a niche trick until you’ve solved three problems with them — then you start seeing “set of strings sharing prefixes” everywhere.

Up next: Day 19 — Segment Trees, the other heavy-machinery structure, for range queries over arrays.

Reverse Bits Introduction

Finished this page?