Drawing binary trees

Introduction

In this post, I’ll lay out a simple algorithm which can be used to draw binary trees – it can be extended to draw other tree types as well. To be clear, a binary tree is a tree data structure in which each node has at most two children (Wikipedia).

As is convention, we’ll be drawing the tree top-down with the root at the top and I’ll use “left” and “right” to designate the left and right children of a node respectively. To make things easier, let us assume each node has a fixed diameter, d. We also want each node in the same level of the tree to be centered at the same vertical position, so we’ll define h to represent the separation between levels. Finally, we want subtrees to be at a distance w from each other (assume w is always greater than d). The following diagram clarifies the convention I’ve chosen.

tree_conventions
Diameter (d), level height (h), and child separation (w)

Notice that I’ve drawn boxes around the nodes. I’ll refer to those as bounding boxes and you’ll understand their usage shortly.

 


Measuring

In order to position a node, we need to know how large its children are so that we can center it. This naturally tends to recursion because to know how large a child is, we will need to know how large its children are also and so on till we get to a leaf node whose size is d x d. We will use the width and height of a bounding box to represent this size. Do remember that the bounding boxes of the left and right children are separated by a distance w.

In other words, we need to do a post-order traversal of the tree and in each step, we obtain the size of a sub-tree. If you’re not familiar with it, this means you visit the left node first, then the right node and then the current node (L-R-C). Here’s the pseudocode:

function setSize() : void
  if left is not null then left.setSize()
  if right is not null then right.setSize()

  if both children are not null then
    width = left.width + w + right.width
    height = h + max(left.height, right.height)
  else if left is not null then # left child only
    width = left.width + (w + d) / 2
    height = left.height + h
  else if right is not null then # right child only
    width = right.width + (w + d) / 2
    height = right.height + h
  else # leaf node
    width = height = d
  end if
end function

tree_measuring

As an illustration, consider the diagram above. The labels indicate the order in which the bounding rectangles are measured.

  1. At the root, you call left.setSize() which then calls left.setSize() and finally we get to node H. Since H is a leaf node, it’s size (width x height) is d x d.
  2. Since D has no left node, we add  half the separation and half the diameter to get its width. It’s height is simply H’s height + h.
  3. Since this is a post-order traversal, the next node to measure is E and since it’s a leaf node, it’s size is also d x d.
  4. The width of B is then sum of the widths of it’s sub-trees and w and it’s height is the greater of the heights of its children plus h.
  5. We then go to the right sub-tree of A (the tree rooted at C). This calls left.setSize() and since F is a leaf node, it’s size is d x d.
  6. At the right of C is G and we go to it’s left I which is a leaf node – d x d.
  7. The size of G is calculated in a fashion similar to that of D
  8. C’s size is calculated similar to B’s.
  9. A’s size (which is the size of the tree) is calculated in a manner similar to B.

Positioning and Drawing

Once the tree’s size has been accurately determined, the next step is to position and draw each node. The algorithm we use here assumes that the x and y coordinates of the center of the current node is specified. Using this information, we then figure out how to place the children so that the current node appears to be in the middle of it’s bounding box.

Here’s a summary:

  1. If a node has a left child only or right child only the horizontal distance between the center of the node and that child (w + d) / 2
  2. If it has both children, then the placement of the children, depends on the placement of nature of the subtree rooted at its children.
    1. If the child has both children, then place it such that it is centered in its bounding box.
    2. If it has a single child, then it should be positioned at either the left or right end of its bounding box depending on which child it has (see image above for clarification.
    3. If it a leaf, center it in its bounding box.
function drawNode(x: real, y: real)
  # draw this node
  if both children are not null then
    # next level is h below current
    childY = y + h

    # center both children in their bounding boxes
    # left end of bounding box
    leftStart = x - width
    if left has both children then
      leftX = leftStart + left.width / 2
    else if left has a left child then
      leftX = leftStart + left.width - d / 2
    else
      leftX = leftStart + d / 2 # position at top-left of bounding box
    end if

    # right end of bounding box
    rightEnd = leftStart + width
    if right has both children then
      rightX = rightEnd - right.width / 2
    else if right has a right child then
      rightX = rightEnd - right.width  + d / 2
    else
      rightX = rightEnd - d / 2
    end if

    left.drawNode(leftX, childY)
    right.drawNode(rightX, childY)
    # draw lines connecting the children to the current node
  else if left is not null then
    leftX = x - (w + d) / 2
    left.drawNode(leftX, childY)
    # draw line connecting left node to this node
  else if right is not null then
    rightX = x + (w + d) / 2
    right.drawNode(rightX, childY)
    #draw line connecting right node to this node
  end if
end function

Finally, since we all love to see proofs of concept, here’s a GitHub repository that demonstrates a working version of the algorithm implemented in C# using WPF. I hope you found this to be helpful!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s