HectorCorrea.com

# Drawing a Binary Tree in CoffeeScript

A few months ago I wrote a small CoffeeScript program to draw binary search trees on a web page page using the HTML 5 Canvas element and was very pleased with clarity and structure of the resulting code. This blog post elaborates on the code structure and how it compares to previous implementations of the same idea that I have done in other languages.

I’ve written programs to draw binary search trees before in C# and Ruby and I wasn’t sure how a CoffeeScript implementation would compare against implementations in more traditional object oriented programming languages. Thanks to CoffeeScript’s support for classes the structure of this implementation is pretty much as you would expect: a BinaryNode class to hold node data, a BinaryTree class to implement the basic binary search tree operations (add, walk), and a BinaryTreeDrawer to calculate the coordinates where each of the nodes should be drawn.

In addition, since this project requires only client-side code (I don’t store the binary search tree data in a server database) it’s was very pleasant not having to deal with a context switching between a “client side” mental model and a “server side” one. This is uncommon in real life projects but it was a nice bonus for a pet project like this.

You can see a running version of this project here. The full CoffeeScript (and JavaScript) source code is available on github.

## 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 tree in this blog post are in fact references to binary search trees.

## Basic Structure of the Code

The main classes that I used to implement the binary search tree drawer functionality are BinaryNode, a BinaryTree, and a BinaryTreeDrawer.

The BinaryNode class is just a small “data class” that stores the information about each node, namely the value of the node and pointers to the node to the left and right of it (gist).

```class BinaryNode
constructor: (@value) ->
@left = null
@right = null

root = exports ? window
root.BinaryNode = BinaryNode
```

The BinaryTree class implements the functionality to add nodes to the tree and walk the tree. The add method takes care of adding each new value to the tree and updating the other nodes accordingly. The walk method goes through each node of the tree in-order and calls another function to allow you to decide what to do on each node (e.g. print it to the screen.)

The code for this class is shown below. Notice that this is just a partial implementation of a binary search tree since it only implements the add and walk methods but is missing functionality to remove nodes, search for values, find the min and max values in the tree, et cetera.

```{BinaryNode} = require?("./binary_node") or window

class BinaryTree

constructor: (rootValue) ->
@root = new BinaryNode rootValue
@count = 1

newNode = new BinaryNode value
node = @root
loop
if value >= node.value
if node.right is null
node.right = newNode
break
else
node = node.right
else
if node.left is null
node.left = newNode
break
else
node = node.left

@count++

walk: (callback) ->
@walkFromNode(callback, @root)

walkFromNode: (callback, node) ->
@walkFromNode(callback, node.left) unless node.left is null
callback(node)
@walkFromNode(callback, node.right) unless node.right is null

toString: ->
values = []
@walk (node) -> values.push node.value
values.join(', ')

root = exports ? window
root.BinaryTree = BinaryTree
```

The BinaryTreeDrawer class walks through the nodes of the tree and calculates the coordinates where each of them should be drawn. This class does not draws the tree per-se, rather it calls a function of your choosing with the coordinates where the node should be drawn.

```{BinaryTree} = require?("./binary_tree") or window

class BinaryTreeDrawer

constructor: (@tree, @distanceX=20, @distanceY=20) ->

# Draws a binary tree (always starts at the root)
draw: (x, y, callback) ->
@drawNode @tree.root, x, y, callback

# Draws a binary tree starting at the specified node
drawNode: (node, x, y, callback) ->
return if node is null
callback node.value, x, y, x, y
@drawLeft node.left, x, y, callback unless node.left is null
@drawRight node.right, x, y, callback unless node.right is null

drawLeft: (node, parentX, parentY, callback) ->
if node.right is null
count = 0
else
count = 1 + @childrenCount node.right

x = parentX - @distanceX - (count * @distanceX)
y = parentY + @distanceY
callback(node.value, x, y, parentX, parentY)

@drawLeft node.left, x, y, callback unless node.left is null
@drawRight node.right, x, y, callback unless node.right is null

drawRight: (node, parentX, parentY, callback) ->
if node.left is null
count = 0
else
count = 1 + @childrenCount node.left

x = parentX + @distanceX + (count * @distanceX)
y = parentY + @distanceY
callback node.value, x, y, parentX, parentY

@drawLeft node.left, x, y, callback unless node.left is null
@drawRight node.right, x, y, callback unless node.right is null

childrenCount: (node) ->
count = 0
count += 1 + @childrenCount node.left unless node.left is null
count += 1 + @childrenCount node.right unless node.right is null
count

root = exports ? window
root.BinaryTreeDrawer = BinaryTreeDrawer
```

## Console Application

File binary_console.coffee shows a very sample of usage of the BinaryTree and BinaryTreeDrawer classes. This console application creates a binary search tree, adds a few nodes to it, and outputs to the console the coordinates where each of these nodes should be drawn.

```# Node.js console demo program for the BinaryTree and BinaryTreeDrawer
{BinaryTree} = require('./binary_tree')
{BinaryTreeDrawer} = require('./binary_tree_drawer')

# Create a binary tree
tree = new BinaryTree(100)
console.log "Values = #{tree.toString()}"

# "Draw" the tree (i.e. output each nodes' coordinates to the console)
console.log "Coordinates"
drawer = new BinaryTreeDrawer(tree)
drawer.draw 100, 100, (v, x1, y1, x2, y2) ->
console.log "#{v} (#{x1}, #{y1}) / (#{x2}, #{y2})"
```

If you have CoffeeScript installed on your box you can just run “coffee binary_console” and you’ll see an output similar to this:

## The Demo Web Page

Once I implemented the BinaryTreeDrawer it was easy to hook this to a web page and actually draw a binary search tree using the HTML 5 Canvas element. The callback passed to the drawer code in this case actually draws circles and lines for each node rather than just outputting the result to the console. Below is a snippet of the code found in binary_web.coffee that shows the basic code to draw the tree:

```drawNode = (v, x1, y1, x2, y2) ->

rootNodeColor = "#4CC552" # green
nodeColor = "#FDD017"     # yellow

color = nodeColor
color = rootNodeColor if x1 is x2 and y1 is y2
color = lastNodeColor if v is lastValueAdded

drawLine x1, y1, x2, y2
drawCircle x1, y1, nodeSize, color
drawLabel x1, y1, v

\$ ->
# initialize the binary tree with some data..
tree = new BinaryTree 100

offsetX = 30
offsetY = 30
drawer = new BinaryTreeDrawer tree, offsetX, offsetY

startX = canvasWidth / 2
startY = 30
drawer.draw startX, startY, drawNode
```

## Final Thoughts

As I said at the beginning of this blog post, I was very pleased with how succinct the code in CoffeeScript to implement a binary search tree drawer ended. The clear and concise CoffeeScript syntax aided with CoffeeScript support for a traditional way of defining classes (while behind the scenes using JavaScript prototypes) resulted in code that is both easy to write, test, and maintain.

## Related posts

Blog posted on: 2012-05-22 02:24:00 +0000 UTC