Suffix Tree
A compressed trie of all suffixes; answers substring queries in O(m).
From the root, the edge "b" leads into a chain of 5 nodes that each have one child and end no word. Nobody can branch off inside it, so the whole chain becomes a single edge labelled "banan$". 5 nodes gone.
What you will see
Every root-to-leaf path is a suffix; a query walks one path.
Cost
| build | O(n) |
|---|---|
| substring query | O(m) |
| Space | O(n) |
Linear construction (Ukkonen) is out of scope for visualization in V1.
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
Related
Taught by the same lesson
Radix Tree, Suffix Tree, Aho-Corasick covers these too, in the same run.