How to Learn Reingold–Tilford Tree Layout: Tidy-Tree Aesthetics, Contours, Modifiers, Two-Pass Coordinates and Linear-Time Engineering

Why can a tree be perfectly correct as data and still look terrible when you draw it? A naïve layout can waste space, break symmetry, overlap labels or make identical subtrees look different depending on where they appear. Reingold–Tilford tree layout treats those visual defects as algorithmic problems and builds a tidy hierarchy by positioning subtrees as coherent geometric objects.

This article teaches tidy-tree layout as a Learning Hall progression from hand-drawn family trees to professional hierarchy visualisation. It complements the Fruchterman–Reingold article, which owns force-directed layout for general graphs. Reingold–Tilford’s distinct job is deterministic rooted-tree placement using subtree shape, contours and accumulated coordinate shifts.

Quick Read

A tidy tree keeps nodes at meaningful levels, preserves child order, centres parents over children, avoids subtree overlap and tries to use space compactly.
The algorithm does not position every node independently. It lays out whole subtrees and shifts them relative to neighbouring subtrees.
Contours describe the leftmost and rightmost occupied positions of a subtree at each depth.
Preliminary coordinates record local horizontal placement.
Modifiers defer subtree-wide shifts instead of immediately updating every descendant.
A later traversal accumulates those modifiers into final coordinates.
Walker generalised tidy-tree ideas to arbitrary-degree trees; Buchheim, Jünger and Leipert showed how to implement the Walker-style method in linear time.
D3’s current tree layout uses the Reingold–Tilford tidy algorithm improved by Buchheim and colleagues.

1. Beginner Level: What Does “Tidy” Mean?

A tree drawing is not merely a collection of x and y coordinates. It communicates ancestry, sibling order and repeated structure. Reingold and Tilford’s classic work formalised aesthetic goals that make a rooted tree readable.

Nodes at the same depth should normally appear on the same horizontal level.
A left child should appear to the left of a right child.
A parent should be centred over its children when the geometry permits.
Subtrees should not overlap.
Identical subtrees should be drawn identically regardless of where they occur.
Mirror-image trees should produce mirror-image drawings.
The drawing should avoid unnecessary width.

These are not decorative afterthoughts. They are constraints on the coordinate-generating algorithm.

2. Why the Obvious Recursive Drawing Can Fail

A first attempt might place each left child one unit left of its parent and each right child one unit right. That works for a tiny balanced tree, but deeper subtrees can collide. Another attempt may lay out each subtree independently and place the second subtree after the full width of the first. That prevents overlap but can waste enormous horizontal space.

The real problem is not the root positions. It is the shapes of the subtrees below them. Two subtrees can often move much closer together because their widest parts occur at different depths.

3. Contours: Compare Shapes One Level at a Time

For any subtree, imagine tracing its outer boundary. At each depth relative to the subtree root, record the leftmost and rightmost occupied horizontal position. These sequences form the subtree’s left and right contours.

When placing one subtree beside another, compare the right contour of the left subtree with the left contour of the right subtree. At every depth where both exist, calculate the separation needed to prevent collision. The maximum required separation determines how far the new subtree must shift.

depth 0: left right-edge = 1,  new left-edge = 0  → need shift 2
depth 1: left right-edge = 2,  new left-edge = 1  → need shift 2
depth 2: left right-edge = 1,  new left-edge = 1  → need shift 1

required shift = max(2, 2, 1) = 2

The exact units depend on the desired node separation. The reusable idea is that spacing is determined by the worst contour collision, not by total subtree width.

4. Preliminary Coordinates: Position Locally First

Tidy-tree algorithms typically separate local positioning from final absolute positioning. During a first traversal, a node receives a preliminary horizontal coordinate based on its siblings and children. For a leaf, that may simply be a position after its previous sibling. For an internal node, the desired location is usually the midpoint of its outermost children.

But a parent cannot always move directly to that midpoint without disturbing spacing already established among siblings. The solution is to keep the preliminary position and store a deferred correction—a modifier—that descendants will inherit later.

5. Modifiers: Move a Whole Subtree Without Touching Every Node

Suppose a subtree must move six units right. The expensive approach is to visit every node in that subtree immediately and add six to its x coordinate. If this happens repeatedly during layout, the same descendants can be updated many times.

A modifier stores the shift at the subtree root. During a later traversal, the algorithm carries the sum of all ancestor modifiers downward. The final coordinate becomes something like:

final_x(node) = prelim(node) + sum(modifiers on path from root to node)

This is a classic algorithm-engineering move: delay repeated range updates and accumulate them once when the final values are needed.

6. Apportionment: Resolve Conflicts Between Neighbouring Subtrees

The step often called apportionment compares the current subtree with its left-side neighbours. If their contours collide, the current subtree is shifted. More sophisticated implementations distribute some movement among intervening siblings so that spacing remains balanced rather than pushing all correction into one place.

This is where tidy-tree layout becomes more than “centre every parent.” A locally centred parent may belong to a subtree that must move globally because another subtree occupies the same horizontal territory at a deeper level.

7. Two Traversals: Build Relative Geometry, Then Resolve It

First walk: process children, establish preliminary x positions, compare contours, shift subtrees, and record modifiers.
Second walk: traverse from the root while accumulating modifiers to produce final x coordinates. Depth naturally supplies y.

This separation makes the method easier to reason about. The first walk solves relative geometry. The second converts that relative state into absolute coordinates.

8. Conceptual Pseudocode

first_walk(v):
    if v is a leaf:
        prelim[v] = position_after_previous_sibling(v)
        return

    for child in children(v):
        first_walk(child)
        apportion(child, previous_siblings)

    midpoint = midpoint_of_outer_children(v)

    if v has a previous sibling:
        prelim[v] = position_after_previous_sibling(v)
        modifier[v] = prelim[v] - midpoint
    else:
        prelim[v] = midpoint

second_walk(v, accumulated_modifier, depth):
    x[v] = prelim[v] + accumulated_modifier
    y[v] = depth

    for child in children(v):
        second_walk(child,
                    accumulated_modifier + modifier[v],
                    depth + 1)

This is intentionally conceptual. Production Walker/Buchheim-style implementations add bookkeeping for ancestors, threads, shifts and changes so contour comparisons can be maintained efficiently for arbitrary-degree trees.

9. Why Threads Appear in Efficient Implementations

While comparing contours, one side of a subtree can end before the other. Efficient tidy-tree algorithms use temporary links often called threads to continue contour traversal without adding real parent-child edges to the tree. These links help the algorithm jump between relevant contour nodes instead of rescanning entire subtrees.

Threads are an implementation aid, not part of the logical input tree. Learners should master contours and modifiers before studying thread bookkeeping; otherwise the mechanism obscures the reason it exists.

10. From Reingold–Tilford to Walker to Buchheim

Reingold and Tilford’s 1981 paper presented a tidy drawing method for binary trees and discussed extensions. Walker later proposed a general-node-positioning algorithm for trees of arbitrary degree. However, the straightforward Walker implementation can take quadratic time on some trees.

Buchheim, Jünger and Leipert showed how to retain the Walker-style layout while implementing it in linear time. Their method organises the required subtree shifts so each node participates in only bounded work across the traversals. This linear-time improvement is the form widely used in contemporary visualisation libraries.

11. Complexity: Why O(n) Matters for Interactive Trees

A modern Buchheim-style tidy-tree layout runs in O(n) time for n nodes, with O(n) storage for node state and output coordinates. Linear time matters when a hierarchy is recalculated repeatedly during interaction, filtering, expansion or resize operations.

But algorithmic O(n) does not guarantee a fast visualisation. Measuring text, constructing DOM/SVG elements, routing links and animating thousands of objects can dominate the total frame time. Professional profiling must separate coordinate computation from rendering.

12. D3: A Production Tidy-Tree Interface

D3’s hierarchy module documents d3.tree() as producing a tidy node-link layout using the Reingold–Tilford algorithm improved to linear time by Buchheim and colleagues. A minimal example is:

const root = d3.hierarchy(data);

const tree = d3.tree()
  .nodeSize([60, 90]);

tree(root);

for (const node of root.descendants()) {
  console.log(node.data.name, node.x, node.y);
}

size and nodeSize express different layout intentions, and D3 also allows a custom separation function. Learn those coordinate semantics before attaching a renderer; otherwise spacing problems can be mistaken for algorithm failures.

13. Variable Node Sizes Change the Geometry

The simplest tidy-tree model treats nodes as points with a fixed separation. Real diagrams contain labels, icons, cards or boxes of different width and height. If the algorithm separates centres but ignores extents, two “non-overlapping” coordinates can still produce overlapping rectangles.

Later work, including van der Ploeg’s non-layered tidy-tree approach, addresses variable-sized nodes while retaining linear-time behaviour. A production system should decide whether layout is point-based, fixed-box, variable-box, layered or non-layered before choosing its collision metric.

14. Reingold–Tilford Versus Fruchterman–Reingold

The similar surnames hide very different algorithmic jobs.

Reingold–Tilford: rooted trees, hierarchical levels, deterministic relative placement, subtree contours, typically linear-time coordinate calculation.
Fruchterman–Reingold: general graphs, iterative attractive/repulsive forces, approximate equilibrium, no requirement that the input be a tree.

If your data has a meaningful parent-child hierarchy, exploiting the tree structure usually produces more stable and interpretable results than pretending the hierarchy is an arbitrary graph.

15. Failure Modes Strong Learners Should Test

Ignoring node width: centre coordinates may be separated while rendered labels overlap.
Unstable child ordering: input order changes can make the diagram jump even when structure is almost unchanged.
Wrong midpoint: centring over all descendant widths is not the same as centring over the relevant children.
Modifier mistakes: forgetting to accumulate ancestor shifts moves deep nodes to incorrect positions.
Contour off-by-one errors: comparing different relative depths creates unnecessary gaps or collisions.
Quadratic rescanning: repeatedly walking whole contours or subtrees defeats the linear-time design.
Forest input: multiple roots need a virtual super-root or an explicit forest-layout policy.
Deep recursion: a highly skewed tree can overflow a language’s call stack even though the algorithm is O(n).
Collapsed nodes: interactive layouts need a policy for hidden descendants and stable transitions.
Assuming radial layout is a different topology: many radial trees simply map tidy-tree coordinates into angle and radius after the hierarchical layout.

16. Professional-Level Engineering

Production hierarchy visualisation adds concerns that the pure coordinate algorithm does not solve by itself. Text must be measured, long labels may need wrapping, links must avoid obscuring nodes, keyboard navigation should follow a meaningful order, and very large trees may need virtualisation or progressive disclosure.

For interactive interfaces, stable coordinates can matter more than absolute compactness. If expanding one branch causes unrelated branches to jump across the screen, users lose their mental map. A professional implementation may preserve previous positions, animate changes, pin selected nodes or constrain subtree movement even when a mathematically tighter packing exists.

17. How to Learn It Without Memorising It

Tidy-tree layout is ideal for visual tracing. Before coding, draw two neighbouring subtrees on graph paper, mark their contours, calculate the minimum non-overlap shift, then predict the parent midpoint. Only after that should the learner encounter modifiers and threads.

Predict: sketch the coordinates a naïve “left −1, right +1” rule would produce.
Run: compute left and right contours of two small subtrees.
Investigate: identify the depth that forces the maximum separation.
Modify: add a deep grandchild on one side and predict which subtree moves.
Make: implement preliminary coordinates plus a second modifier-accumulation traversal.
Validate: test mirror symmetry, repeated identical subtrees, chains, stars, balanced trees and highly irregular trees.

18. Learning Progression: Beginner to Professional

Beginner: define tidy-tree aesthetics and manually place a small binary tree.
Intermediate: calculate contours, subtree shifts, preliminary coordinates and modifiers.
Advanced: study Walker/Buchheim apportionment, threads and the proof of linear-time work.
Professional: support variable node sizes, stable interaction, forests, deep trees, viewport constraints, renderer performance and accessibility.

19. Practice Problems

Draw a tree for which fixed ±1 child offsets cause overlap.
Compute the two contours of a seven-node subtree by hand.
Given two contour arrays, calculate the minimum horizontal shift for a separation of one unit.
Construct a tree and its mirror. Verify that your layout coordinates mirror exactly around the root.
Instrument a naïve contour-rescanning implementation and find an input on which its work grows quadratically.
Use D3 tree().nodeSize(...) on the same hierarchy with three separation functions and compare the geometry.
Add variable-width labels and test whether centre-to-centre spacing still prevents overlap.

20. Sources and Further Reading

Final idea: Reingold–Tilford teaches that layout is not “put coordinates on nodes.” It is a constrained optimisation of relationships people need to see. By treating a subtree as a shape with a contour, the algorithm converts visual tidiness into structure that can be reasoned about, deferred, composed and computed efficiently.

Small Group Tutorials