Visualizing Ukkonen's Suffix Tree Algorithm (opens in new tab)

Author here. It’s a very hopeful time for interactive learning. Coincidentally, it is inspiring that both OpenAI and Anthropic released these improved visualization capabilities just this week.

Using Gemini's canvas for chord progressions is a great example of this. When I was building this suffix tree visualizer, I kept thinking about how much "spatial" intuition is required to understand the algorithm; having these live, interactive environments available to students is a massive step forward.

https://openai.com/index/new-ways-to-learn-math-and-science-... https://claude.com/blog/claude-builds-visuals

I totally fell for the "obscene memory" trap myself. My first encounter with suffix trees outside of a textbook was for an ITA Software 'Instant Search' puzzle. The requirement was sub-0.1ms search on a large string database, I went straight for a generalized suffix tree. Then I realized they had asked for the solution to fit within a 1GB heap. :(

I wrote up the full 'war story' of how I had to profile the heap and optimize the node representation (shaving bytes off the edge storage) just to get it to boot without an OOM error: https://www.abahgat.com/blog/the-programming-puzzle-that-got...

It’s the most tangible example I've run into of where theoretical O(n) space complexity meets the reality of object pointer overhead.

I've never grokkeed suffix trees, but isn't possible for them to be O(n) in space (n total length of all strings)? Is there just an unacceptable constant factor overhead? I can imagine the pointer overhead being painful.

Yes, we get the same speed from suffix arrays these days, and much, much less memory usage.

But good luck visualizing what those algorithms do :)