Trie
A tree with one node per character, so every path from the root spells a prefix and words share their common prefixes.
Decision · step 2 of 19Trie: Insert words sharing prefixes
"car", letter 'c'. No child 'c' yet, so create one and step into it.
What you will see
Insert walks existing edges then sprouts new ones; the terminal node gets a marker.
Cost
| insert | O(L) |
|---|---|
| search | O(L) |
| prefix query | O(L + results) |
| Space | O(total characters * alphabet) |
L is the word length.
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, try operations in any order.
Screen readers: Each element is an accessibility element with position, value and state; structural changes are announced per step.
Reduced motion: Elements appear at their destination with a crossfade; no travel longer than the element's own size.
Before this
Taught by the same lesson
Trie covers these too, in the same run.