Drawing a Binary Tree in Ruby

When I started learning Ruby last year I decided to implement a binary tree and some of its basic operations (insert, delete, walk, and search) just to get my feet wet on the language. Binary trees are a good exercise because you need to use several features of the language like conditional statements, loops, and classes while at the same time you are solving an interesting problem. The algorithm for binary trees is well documented in most introductory books on algorithms and on the web.

To make things a bit more challenging I also implemented a program to draw the binary tree so that people can see how a binary tree looks like when it has more than just a handful of nodes. In this particular case I wrote small a web application in Ruby that draws the binary tree using the new canvas element supported in HTML 5. You can see a live demo of the Ruby web site which allows you to draw binary trees with our own set of values or you can just let it draw binary trees with random values. For demo purposes trees on the demo site are limited to 250 nodes but you can draw much larger trees if you download the code and host it on your own.

This blog post gives short overview of the main methods to implement the binary tree, the algorithm to draw the binary tree, and the web site to demo the drawing algorithm.

Binary Tree or Binary Search Tree

Properly speaking the code in this blog post implements a Binary Search Tree (BST) which is a more specific version of a Binary Tree. Cormen et al. give a good explanation of this on their book Introduction to Algorithms. Binary trees are trees in which each node has at most two children, one of them called "left subtree" and the other called "right subtree" but there is no order enforced per-se (pp. 1178). Binary Search Trees on the other hand are always stored in a way as to satisfy the binary-search-tree property (pp. 287):

Let x be a node in a binary search tree. If y is a node in the left subtree of x, then y.key ≤ x.key. If y is a node in the right subtree of x, then y.key ≥ x.key.

I took a bit of a liberty on this blog post (and its related source code) and use both terms interchangeably. Please be aware that all of the references to binary search in this blog post are in fact references to binary search trees.

Implementing a Binary Search Tree

The procedures to implement the basic binary search tree operations like insert, delete, search, and walk are well documented in most introductory books on data structures and algorithms and on the web (e.g. www.algolist.net and wikipedia) and they are fairly easy to implement in Ruby.

The class that I implemented can be used as follows:

Out of the box we can use this BinaryTree class with numbers or strings or any other native Ruby type. We can also use it with other types as long as they implement comparable operations (i.e. def <=>).

Adding Nodes to a Binary Tree

The code to add nodes to the binary tree is shown below. This code first evaluates if we already have a root node, if we don't then we create a root node with the new value and we are done. If we already have a root node then scan the nodes of the tree (using the binary-search-tree property aforementioned, smaller values go to the left, equal or greater than values go to the right) until we reach a leaf node. Once we've reached a leaf node we update it to point to the new node.

Walking the Tree

One of the advantages of a binary search tree is that it's very easy to retrieve in order the values stored on it. This process is called "walking the tree in order". For example, if we have a tree with the following values: 100, 50, 200, and 150 walking the tree in order will give us: 50, 100, 150, and 200. Walking the tree can be implemented easily with a recursive function. However the recursive method, although elegant, it's not very efficient when the tree is expected to have a large number of nodes. The code that I implemented to walk the tree does not use recursion but instead uses an array as a stack to keep track of the nodes that it visits. This version is not as elegant as the recursive version found in most introductory books but it works well even when the tree has thousands of nodes.

Below is the code for walking the tree in order that I implemented.

While implementing this method I got to experience first hand the beauty and simplicity of one of Ruby's most touted features: blocks. You can see the use of blocks in the line yield node of the previous code. As the algorithm finds the next node to process it simple yields it to the caller program. This allows the code to walk the tree to be completely independent from the action that we want to perform on each node. For example, we can print each node to the console with the following code:

tree.walk { |node| puts "#{node.value}" }

In this example the block is a simple "puts" statement but we'll see a more sophisticated example of this when we review the code to draw the binary tree. This kind of decoupling between the iteration of the elements in the tree and the action to execute on each of them can be implemented in other programming languages via delegates or pointers but I was amazed on how simple and elegant it was to do this in Ruby.

How to Draw a Binary Tree

The algorithm to draw a binary tree that I implemented is pretty much a variation of the algorithm to walk the tree with the exception that we need to calculate the coordinates where each node needs to be placed as we traverse the nodes in order. Calculating the coordinates turned out to be an interesting challenge but a final simple solution.

The basics of this algorithm are as follow:

• Draw the root node in the coordinates indicated.
• Draw the left subtree to the left of the root node.
• Draw the right subtree to the right of the root node.

To calculate the coordinate where the left subtree should be drawn we count how many children the right side of the left subtree has. We use this number to calculate the x-coordinate as a negative offset from the root. The y-coordinate is simple a positive offset from the root. Then we recurse this process for the left subtree and right subtrees. The following code snippet shows this code.

The procedure to calculate the coordinate where the right subtree should be drawn is just the reverse: we count how many children the left side of the right subtree has. We use this number to calculate the x-coordinate as a positive offset from the root. The y-coordinate is simple a positive offset from the root. Then we recurse this process for the left subtree and right subtrees. The following code snippet shows this code.

Like in the walk method, the three draw methods presented here only calculate where the node should be drawn but they don't actually draw the node. Instead they call a block with the appropriate parameters to perform the actual operation. You can see this in the line block.call(node.value, x, y, parent_x, parent_y) in these three routines.

The following code shows an example of calling the draw method on a simple tree and displaying on the console the coordinate where each of the nodes should be drawn

There is plenty of research on the best way to draw binary trees with lots of data. The book Graph Drawing: Algorithms for the Visualization of Graphs by Tollis et al. seems to be the reference that most research papers and presentations cite. On pages 43-45 they provide a more sophisticated version of the algorithm that I used plus several advanced algorithms for different scenarios.

Perhaps in the future I'll update my code to implement the enhancements suggested by Tollis et al. and also to remove the recursive calls from my implementation.

A Real Example of Drawing a Binary Tree on a Web Page

Once we have the coordinates where each node can be drawn we could use any graphic program to perform the actual drawing. Since I wrote this program as learning exercise I decided to write a small Ruby web application to do the actual drawing. In this web application I use the new HTML 5 canvas element as the drawing surface and a series of JavaScript calls to draw lines and circles on the appropriate coordinates.

The following code shows a simplified version of how I generate the JavaScript calls to draw the nodes (circles and labels) and lines connecting the nodes.

Notice that this code merely creates three arrays (circles, lines, labels) with some JavaScript calls. These arrays are later inserted on a web page so that when the user renders it the tree is drawn on their browser.

Source Code and Live Demo

If you want to the see this code running you can visit http://binarytree.heroku.com and generate a few binary trees with random data or draw a binary tree with your own set of data.

The demo site is limited to 250 nodes but on my local environment I've drawn trees with up to 10,000 nodes. One of the disadvantages of the drawing algorithm that I implemented is that it's not an area-efficient algorithm which leads to very wide drawings. You can see this effect in this tree with 500 nodes. A more dramatic example is a tree with 5,000 nodes that I generated with this code too. If I were to print this tree it would be 115 feet long by 1 foot tall (as a reference, a basketball court is 94 feet long!) You can download this tree from http://downloads.hectorcorrea.com/tree5000.png but be aware that it's almost 4MB in size and it might crash your browser when trying to display it (which is why I am not making it a hyperlink.)

You can find the entire Ruby source code to implement the binary tree and the binary tree drawer, as well as the demo web site on github at https://github.com/hectorcorrea/binary-tree. Feel free to check it out and let me know what you think.

Related Post

• Drawing a Binary Tree in CoffeeScript