Building a binary search tree in Javascript

“A tree’s a tree. How many more do you need to look at?” – Ronald Reagan

I am reading Secrets of the Javascript Ninja by John Resig and wanted to try out some of the more advanced Javascript concepts.  I also wanted to do something more than just a ‘hello world’ so I decided to build a binary search tree (bst).

Beauty and the BST

There are many articles out there on BST’s so I will skip going into that here.  What I am interested in building is a simple node ‘object’ in JS that can hold references to its left and right children.  To do this, I decided to use the JS prototype functionality.

// Name and value can be set at creation time so are passed into the constructor
function Node(name, value) {
     this.name = name;
     this.value = value;
}

Node.prototype.setLeft = function(left) {
     this.left = left;
}

Node.prototype.setRight = function(right) {
     this.right = right;
}

BST Insertion Logic

Next up is creating the logic that adds a new node to the right place in the BST.  We are not going to get into rebalancing so it is very possible that this tree is waaaay overweighted on one side.  We will live with that and maybe get to that in a future exercise.

// tree is the root node of the tree.  node is the new node to add
// If the new node is greater than tree, then we either add it as the right child if tree does not have a child, otherwise, we call insertNode again but this time passing in tree's right child as the tree parameter.  Similar logic is done if node is less than tree.

function insertNode(tree, node) {
    if (tree) {
        if (tree.value < node.value) {
            if (tree.right) {
                insertNode(tree.right, node);
            } else {
                tree.setRight(node);
            }
        } else {
            if (tree.left) {
                insertNode(tree.left, node);
            } else {
                tree.setLeft(node);
            }
        }
    } else {
        tree = node;
    }
    return tree;
}

Testing the BST Here we do some initial setup in setup, where we add several nodes in various ascending order. Then we print out the tree with printTreeAsc to verify we can walk the tree from lowest to highest, starting from root.

function setup() {
    nodeA = new Node('a', 5);
    nodeB = new Node('b', 12);
    nodeC = new Node('c', 10);
    nodeD = new Node('d', 15);
    nodeE = new Node('e', 20);
    nodeF = new Node('f', 25);
    nodeG = new Node('g', 8);
    nodeH = new Node('h', 3);

    var tree = insertNode(tree, nodeA);
    tree = insertNode(tree, nodeB);
    tree = insertNode(tree, nodeC);
    tree = insertNode(tree, nodeD);
    tree = insertNode(tree, nodeE);
    tree = insertNode(tree, nodeF);
    tree = insertNode(tree, nodeG);    
    tree = insertNode(tree, nodeH);    
}

function printTreeAsc(root) {
    var currNode = root;
    if(currNode.left) {
        printTreeAsc(currNode.left);
    }

    console.log(currNode.value);

    if(currNode.right) {
        printTreeAsc(currNode.right);
    }
}

Running setup() and then printTreeAsc(nodeA) yields:

3
5
8
10
12
15
20
25

It works!
Lastly, how tall is my BST?
BSTs are a fun way to work with algorithms and recursion, so I decided to write a method to calculate the height of the tree. Basically this will return the maximum number of steps from nodeA down to the lowest node. Perfect candidate for recursion!

function calcHeight(node) {
    if (node) {
        return 1 + Math.max(calcHeight(node.left), calcHeight(node.right));
    } else {
        return 0;
    }
}

Result: 5. Passing in nodeA, this gives a result of 5.

Summary
So we got to see the JS prototype feature in action when we build the tree, in insertNode. We also built a simple binary search tree and verified it works by iterating over it in ascending order. And last but not least, we wrote a simple recursive method to determine its height.

Advertisements

Using Node cronjobs to replace Heroku worker dynos

“Time keeps on slipping, slippin…into the future.”  – Steve Miller Band

Hopscotch.fm relies on data that is pulled in from several music related services.  I have created multiple tasks each of which can be run from the command line, like:

node run manualrun getShows sf

This will get the shows for San Francisco. On Heroku, I was using the Scheduler to automatically run this periodically. All good so far.

The Problem

The solution worked great up until I started needing several of these workers, to get shows, to get artist metadata, to get artist songs, cleanup, and more.  Easy enough I thought.  I just added more tasks to the Heroku Scheduler. Except there is a limit to the free tier on Heroku…

The Surprise (the Heroku bill!)

My Heroku bill was over $70!  How did this happen??  Turns out I had exceeded the free monthly hours with all the worker dynos I had been spinning up.  So I needed a solution quick.  I host hopscotch.fm on nodejitsu so I figured why not just use that.

The Solution (cron!)

Enter node-cron. If you’ve ever used Linux/UNIX cron jobs, it’s nearly identical.  The syntax for dates is the same.  All you need to do is specify the function to run.  Here is a cron job in file cronjobs.js that crunches radio stations for a city:

var cronJob = require('cron').CronJob;
var cruncher = require('./cruncher); // internal class that does the crunching
var jobMetroRadio = new cronJob('00 05 00 * * 1-7', (function() {
  console.log('Starting crunching shows.');
  return cruncher.crunchShows(function() {
    return console.log('Finished crunching shows.');
  });
}), (function() {}), true, time.tzset("America/Los_Angeles"));

Then in app.js I just:

require('./cronjobs');

And lastly add these two packages to package.json and install them

cron  // add to package.json
time  // add to package.json
npm install

The Result
I’ve moved all of the tasks over from Heroku Scheduler onto the nodejitsu deployment and everything is running smoothly. Hooray for cron!