Hacker News Reader

Comment by virtuous_signal | Hacker News Reader

So the author mentions hearing about the Reingold-Tilford Algorithm which wouldn't work for the example given since R-T is meant for binary trees and a family tree might have more than 2 nodes.

Which led me to wonder why is there even an "algorithm" per se for binary trees: wouldn't it be acceptable to just trace out a complete binary tree with spaces reserved for each potential node, and only fill in a space with a node if it is non-null? Or does this not meet some criterion of "niceness" for drawings?

View on HN

If you do that, you quickly run into the feasible depth limit for what you can show in a fixed space. Especially for sparse trees. Consider something like family trees, where you generally don't know anything about certain lines, but may have 20 generations or more on selected lines. No way could you show 2^20 nodes in a fixed format rendering, but you can make something kinda pretty by eliminating the empty space and organizing things to fill it intelligently.

I was just writing a radial RT-like visualization for displaying the branching structure of a binary tree and ran into the issue of information density you describe. Still pretty happy with the results, tho, in how it shows the structure and clustering.

And I colored it like a tree, just for fun - https://giphy.com/gifs/TKFUkrWQtil60Ij2YJ/html5

That only works for complete (or "nearly" complete) binary trees, and you can't draw many of these since the number of children in a generation grows exponentially. For most trees you have to try to keep the width minimal while avoiding collisions between deeply-nested left and right children. One of the earlier papers to give some precise "niceness" criteria is "Tidier Drawings of Trees" (https://reingold.co/tidier-drawings.pdf) by Reingold and Tilford, with a companion Pascal program for computing the coordinates.

Fantastic. I would not have thought that binary-tree-drawing could be such a complicated problem.

Graph drawing in general is a field full of complicated problems.

Reply on news.ycombinator.com