The Reingold Tilford Algorithm Explained, with Walkthrough | by Kay Jan Wong | Sep, 2023

The 1981 Reingold-Tilford algorithm creates a visually pleasing illustration of hierarchical data by arranging nodes in a tree development to maximise readability. In several phrases, it’s an algorithm for retrieving the (x, y) coordinates of every node in a tree.

Consistent with the paper, there are a few aesthetic tips {{that a}} good tree diagram must adjust to,

1. Nodes on the same depth must lie alongside a straight line, and the straight strains defining the depths have to be parallel

2. A left baby have to be positioned to the left of its mom or father node and a correct baby to the suitable (solely related to binary timber)

3. A mom or father have to be centered over their children

4. A tree and its mirror image ought to provide drawings that are a reflection of one another, and a subtree have to be drawn the equivalent method regardless of the place it occurs inside the tree

Determining the y coordinates of the nodes is straightforward, whereas the x coordinates are barely additional powerful. This article will attempt to make clear the algorithm with numerical examples on a barely additional sophisticated tree than the alternative papers and articles I’ve study, so additional eventualities could also be coated. I’ll even introduce additional terminologies not used inside the distinctive paper to greater distinguish between the utterly totally different phrases.

An very important intuition in regards to the algorithm is that it’ll plot the tree from a left-to-right route. You’ll be capable of contemplate the leftmost node having a coordinate of (0, 0), and the various subtrees will shift rightwards accordingly.

Pleasing actuality: scikit-learn Python library can be using this algorithm to plot decision timber!

Sooner than determining the last word coordinates of every node, 3 phrases are important. The distinctive paper references the phrases x and mod, nevertheless in my rationalization, I’ll use an additional shift…