Tries — prefix search and autocomplete
A tree keyed by character. Autocomplete, spellcheck, and IP routing tables all live here.
Runs on a sandboxed JVM via the public Piston API. Edit the code and hit Run.
One node per character
A trie (pronounced 'try') stores strings by walking one character per node. Each edge is a character; each root-to-node path spells a prefix. The end flag marks nodes where a stored word terminates. Lookup cost depends only on the query length, never on the number of stored words.
Insert, contains, prefix
insert(word) walks down from the root, creating nodes as needed, and flips end = true at the last one. contains(word) walks the same path and returns end. startsWith(prefix) walks the prefix and returns true if the walk didn't hit a dead end — it doesn't care whether the prefix itself is a stored word.
Autocomplete
Walk to the prefix node, then DFS from there collecting every descendant that has end = true. Rank the results by frequency or recency to build a real autocomplete feature. The trie handles the search space pruning; ranking is your business logic.
Runs on a sandboxed JVM via the public Piston API. Edit the code and hit Run.
Memory vs speed
A HashMap per node is flexible but heavy. For a small fixed alphabet (say lowercase a–z), swap it for a Node[26] — faster and smaller. For very large dictionaries, look up compressed tries (radix trees) or DAWGs (directed acyclic word graphs), which share suffixes across words.
Beyond words
Tries generalize to any sequence of tokens. IP routers use tries over bits for longest-prefix matching. Filesystems use them over path segments. Anywhere you need prefix queries on a large alphabet, the trie is the right shape.
Related lessons & next topics
Keep going — these pair well with Tries.
- § 6.01 · Data Structures in JavaArrays and ArrayList — the workhorses
Fixed-size arrays vs dynamic ArrayList. Memory layout, amortized O(1) append, and when each one shines.
Beginner · 22 min - § 6.02 · Data Structures in JavaLinkedList and the Deque interface
Doubly-linked nodes, O(1) insert at either end, and why LinkedList is almost never the right choice.
Beginner · 20 min - § 6.03 · Data Structures in JavaStacks, queues, and ArrayDeque
LIFO, FIFO, and why java.util.Stack is a historical mistake you should avoid.
Intermediate · 24 min - § 6.04 · Data Structures in JavaHashMap, equals, and hashCode
How hashing works, why you must override equals and hashCode together, and the load factor that keeps lookups O(1).
Intermediate · 28 min