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.