Drawing Trees Functionally: Reingold and Tilford, 1981

April 22, 2023
« Previous post   Next post »


Functional programmers often work with trees; for explanatory or debugging purposes, it is useful to be able to visualize them. I explain one such algorithm for drawing m-ary trees, the Reingold-Tilford algorithm, which runs in O(n)O(n) time. Animations showing the core ideas of the algorithm are provided. I present a reimplementation of the algorithm in Haskell, showing how to implement the algorithm without complicated pointer manipulations, while still preserving the O(n)O(n) time bound.

In Tidier Drawings of Trees, 1981 (PDF), Reingold and Tilford introduce an algorithm for drawing aesthetically pleasing trees. They define specific aesthetics that their algorithm upholds:

  1. Nodes at the same depth in the tree should be drawn at the same vertical level in the output.
  2. A left child should be drawn to the left of its parent, and the right child to the right of the parent.
  3. A parent should be centered over its children.
  4. A subtree should be drawn the same way regardless of where it appears in the tree.

For reference, here's what a tree drawn by the Reingold-Tilford algorithm looks like:

Fig 1. A tree as drawn by the Reingold-Tilford algorithm.

Drawing a tree distills down into assigning (x,y)(x, y) coordinates to each node in the tree such that the coordinates don't overlap, while satisfying the aesthetics defined above. We first look at the simpler case of drawing binary trees, then extend the algorithm to m-ary trees later. Assigning yy coordinates is easy, since for each node we assign its depth to the yy coordinate. For the xx coordinates, the idea is to recursively position the subtrees at each node. At each node, we place the roots of the left and right subtrees on top of each other, then recurse down the contours of the subtrees, pushing the subtrees apart whenever we find that they overlap. Once we finish scanning the contours, the subtrees are as close as they can be without overlapping, so we place the current node as their parent, centered between them.

Fig 2. Animation showing the recursive contour scan at the heart of the Reingold-Tilford algorithm, operating on the tree in Fig 1.

A contour of a tree is all the rightmost or leftmost nodes at each level in the tree. For instance, in the below tree, the nodes in the left contour are marked in red:

Fig 3. A tree with its left contour marked in red. Note how the left contour must include a node on the right side of the tree, since that node is the leftmost at its level!

More formally, the left contour of a tree with height kk is the sequence of nodes n0,n1,...,nkn_0, n_1, ..., n_k such that i.ni=\forall i. n_i = the leftmost node of depth ii in the tree. The right contour is defined symmetrically. Note that this means the contours of a tree are always the same length as the height of the tree, plus one.

Reingold and Tilford split the assignment of (x,y)(x, y) coordinates into two steps: first, we calculate the horizontal distance from each node to either of its children; second, "petrify" the tree by calculating the actual xx coordinates based on each node's path from the root. Calculating the horizontal offsets works by a postorder traversal; at each node, we (1) recursively position and construct the contours for our left and right subtree, (2) figure out how far apart we should space the subtrees (and hence, the offset at the current node) by recursing in lockstep down the right contour of the left subtree and the left contour of the right subtree, (3) construct the contours of the tree rooted at the current node.

Fig 4. A tree separated into the root and its left and right subtrees. The right contour of its left subtree and the left contour of its right subtree are marked in red. We scan level-by-level, following these paths.

Intuitively, it's easy to see why we recurse down the right contour of the left subtree and the left contour of the right subtree: these are the "closest" parts of the subtrees to each other.

Assuming we can follow the contours, the core idea of the paper is simply to go level by level on the subtree contours, looking at the left subtree's rightmost and right subtree's leftmost node on that level. We keep track of how far apart the left and right nodes are, and whenever that distance is too small, we increase the distance at the root to separate the left and right.

Fig 5. Animation of the contour scan on a complete binary tree.

But as you can see from Figs. 3 and 4 above, there may not be a direct link from one node on the contour to the next. So as part of the algorithm, we need to construct a way for us to efficiently follow the contour in that case. The way Reingold and Tilford tackle this is through "threads," pointers from dead-end nodes to the next node on the contour, creating the threads as the recursion unwinds back up the tree. Since those dead-end nodes would typically contain two null child pointers, they reuse one of them to point to the next contour node, creating a path to ensure later traversal is efficient.1

Fig 6. Dashed lines show the path that the contour scan follows. Note how sometimes the contour must follow paths that don't exist in the tree itself.

All the complexity of the paper is how those threads get constructed; once we have a contour to follow, calculating the distances is straightforward. If you're interested in the specifics of that thread construction, I encourage you to read the paper itself; it's only 6 pages! For your benefit, here's my comment-annotated version of the Pascal source code provided in the paper. And as we'll see in the next section, it's not necessary to do this pointer manipulation anyways; there's a much simpler way to recurse down the contours.

As mentioned, the Reingold-Tilford algorithm is O(n)O(n) time in number of nodes in the tree. Extending the algorithm to m-ary trees while preserving this bound is also fairly simple: in each node, store the distance between each adjacent pair of subtrees, and do the same scan as on binary trees to "clump" pairs of subtrees together, calculating how far apart they should be. In other words, fold the scan across all subtrees.

Once More, With Purity

In a purely functional language like Haskell, we can't exactly do the same sort of raw pointer manipulation. Though we can definitely construct a DAG where a node has two parents (one "real" parent and one "thread" parent), updating such a structure is painful at best. What if that thread target then needs to be threaded itself? We would have to update both parents as well, making the recursion impossible to write.

The only reason we need the threads is to provide information about the contours. That suggests an alternative: we could simply construct said contour information directly. For each subtree, we construct two lists of nodes, representing the left and right contours. Thankfully, contours have an easy recursive definition.

Let h(𝒯)h(\mathcal{T}) be the height of tree 𝒯\mathcal{T}. Let contourl(𝒯)=contour_l(\mathcal{T}) = the sequence of nodes in the left contour n0,n1,...,nh(𝒯)n_0, n_1, ..., n_{h(\mathcal{T})}, as defined above. Given a node 𝓉\mathcal{t} with children 𝒯l\mathcal{T}_l and 𝒯r\mathcal{T}_r, let ll=contourl(𝒯l)ll = contour_l(\mathcal{T}_l) and rl=contourl(𝒯r)rl = contour_l(\mathcal{T}_r). Then,

contourl(𝓉)=append(𝓉,ll,drop(length(ll),rl)) contour_l(\mathcal{t}) = append(\mathcal{t}, ll, drop(length(ll), rl))

That is, the left contour of the tree rooted at 𝓉\mathcal{t} always starts with the node 𝓉\mathcal{t}, since the root is the only node at its level and thus leftmost by definition. Then we follow the left contour of the left subtree as far as we can. If the left subtree is shorter than the right subtree, we then follow the left contour of the right subtree for any remaining levels. Remember that the length of a contour for our tree must be the same as the height of the tree + 1, so we cannot just use the left subtree's contour if the right subtree is taller. The definition of contourrcontour_r is symmetrical.

It remains to show that this definition contains the leftmost nodes at each level of the tree rooted at 𝓉\mathcal{t}. Firstly, it contains 1+max[h(𝒯l)+1,h(𝒯r)+1]1 + max[h(\mathcal{T}_l)+1, h(\mathcal{T}_r)+1] == 2+max[h(𝒯l),h(𝒯r)]2 + max[h(\mathcal{T}_l), h(\mathcal{T}_r)] == 1+h(𝓉)1 + h(\mathcal{t}) nodes, which is exactly correct. For each node in contourl(𝓉)contour_l(\mathcal{t}), it is either 𝓉\mathcal{t} itself, a node from llll, or a node from rlrl. As above, 𝓉\mathcal{t} is trivially the leftmost node on its level. If the node is from llll, by definition it is the leftmost node in 𝒯l\mathcal{T}_l at its level, and is trivially to the left of any nodes on that level in 𝒯r\mathcal{T}_r. If the node is from rlrl, 𝒯l\mathcal{T}_l must not have any nodes at its level (since we drop the first part of rlrl), and thus the node is also trivially leftmost at its level. \square

Now that we have a way to construct the contour information, we do a straightforward recursive scan down the sequence of contour nodes, the same way we would if we had thread pointers. The full implementation can be seen here.

I show that this way of implementing the Reingold-Tilford algorithm still runs in O(n)O(n) time. Other than the construction of the contours at each node, the Haskell code above recurses in exactly the same way as Reingold and Tilford's original Pascal code, visiting each node and scanning down the contours. Therefore, we can assume everything excluding the contour construction runs in O(n)O(n) time.

We use the function spliceContours to construct the contours at a node. Calls to this function can be expensive when we need to take some contour nodes from the left subtree and some from the right subtree, due to the calls to list append, take, drop, and length.

-- Since the scan only cares about the distance between the
-- two nodes at the current level, the only info we need about
-- the contour is relative x distance to the next node in the contour
type Contour = [Int64]

data Contours = Contours
  { left :: Contour
  , right :: Contour
  deriving Show

-- Distances calculated while performing the contour scan.
-- lroffsum = the offset from the root to the node in the right contour
--   of the left subtree, which is at the level we stopped the scan at
-- and so on for lloffsum, rloffsum, rroffsum
data ScanResult = ScanResult
  { rootOffset :: Offset
  , lloffsum :: Offset
  , lroffsum :: Offset
  , rloffsum :: Offset
  , rroffsum :: Offset
  deriving Show

spliceContours :: Int64 -> ScanResult -> (Contours, Contours) -> Contours
spliceContours rootOffset scan (Contours ll lr, Contours rl rr) =
  Contours leftContour rightContour
    compareLength :: [a] -> [b] -> Ordering
    compareLength [] [] = EQ
    compareLength [] _y = LT
    compareLength _x [] = GT
    compareLength (_:xs) (_:ys) = compareLength xs ys

    leftContour :: Contour
    leftContour = case (rl `compareLength` ll, ll, rl) of
      (_, [], []) -> [0]
      (EQ, _, _) -> negate rootOffset : ll
      (LT, _, _) -> negate rootOffset : ll
      (GT, [], _) -> rootOffset : rl
      (GT, _, _) ->
        negate rootOffset
          : take (length ll - 1) ll
         ++ (rloffsum scan - lloffsum scan)
          : drop (length ll) rl

    rightContour :: Contour
    rightContour = case (lr `compareLength` rr, rr, lr) of
      (_, [], []) -> [0]
      (EQ, _, _) -> rootOffset : rr
      (LT, _, _) -> rootOffset : rr
      (GT, [], _) -> negate rootOffset : lr
      (GT, _, _) ->
          : take (length rr - 1) rr
         ++ (lroffsum scan - rroffsum scan)
          : drop (length rr) lr

All the expensive functions called by spliceContours take time linear in the height of the shorter subtree, and it calls them a constant number of times. Let us then define

s(𝓉)=min[h(𝒯l),h(𝒯r)] s(\mathcal{t}) = min[h(\mathcal{T}_l), h(\mathcal{T}_r)]

as the cost of spliceContours for constructing the contours at a single node 𝓉\mathcal{t}, and let us define 𝒮(𝒯)\mathcal{S}(\mathcal{T}) as the sum of s(𝓉)s(\mathcal{t}) for all nodes in tree 𝒯\mathcal{T}.

𝒮(𝓉)=𝒮(𝒯l)+𝒮(𝒯r)+s(𝓉) \mathcal{S}(\mathcal{t}) = \mathcal{S}(\mathcal{T}_l) + \mathcal{S}(\mathcal{T}_r) + s(\mathcal{t})

The paper defines the total cost of the recursive scan and contour threading as F(𝒯)+n(𝒯)F(\mathcal{T}) + n(\mathcal{T}), where n(𝒯)=n(\mathcal{T}) = the number of nodes in the tree. They show that F(𝒯)F(\mathcal{T}) is O(n)O(n), and define it recursively as

F(𝒯)=F(𝒯l)+F(𝒯r)+min[h(𝒯l),h(𝒯r)] F(\mathcal{T}) = F(\mathcal{T}_l) + F(\mathcal{T}_r) + min[h(\mathcal{T}_l), h(\mathcal{T}_r)]

If we expand s(𝓉)s(\mathcal{t}) in the definition of 𝒮(𝒯)\mathcal{S}(\mathcal{T}) above, we see that the definition of 𝒮(𝒯)\mathcal{S}(\mathcal{T}) is exactly that of F(𝒯)F(\mathcal{T}). Since 𝒮()=0\mathcal{S}(\bullet) = 0, 𝒮(𝒯)F(𝒯)=O(n)\mathcal{S}(\mathcal{T}) \le F(\mathcal{T}) = O(n). The total cost of the recursive scan is F(𝒯)+𝒮(𝒯)+n(𝒯)F(\mathcal{T}) + \mathcal{S}(\mathcal{T}) + n(\mathcal{T}), which is linear. \square


I use lists for representing the contours to simplify the presentation and implementation of the algorithm. It just so happens that even using linked lists, we still get a linear time algorithm! Happily, this means that the algorithm can easily be implemented in a pure manner even in non-lazy languages, removing the need for complicated pointer manipulations.

But in a real implementation, there's no reason to prefer linked lists over a data structure which supports efficient insertion and catenation. If one expects to be drawing very large trees, storing the contours using a different, persisent data structure like 2-3 finger trees or Okasaki's implicit recursive slowdown deque may prove more efficient.

Technically, the only operations needed are the stack operations, head, tail, and cons. Constructing the new contours can happen at the same time as the contour scan, by consing the correct nodes to the appropriate contours as the recursion unwinds. The implementation would become more complicated, however.

« Previous post   Next post »

Before you close that tab...


↥1 Thinking that this pointer manipulation is gross is a sign of sanity.