David’s Web Development Blog

Nicholas Zakas has a nice writeup on creating a binary search tree in JavaScript as part of his computer science series, where he’s explaining basic CS principles such as bubble sorting and linked lists entirely in JavaScript.  This is a great idea in many ways, most of all because it further separates learning programming from learning a compiler (such as a strictly-typed language like C++).

For a beginner, Nicholas’s writeup will look a bit daunting.  It contains some advanced JavaScript principles that beginners won’t be familiar with (namely prototype), along with some things that make the search tree look unnecessarily complicated on first glance.  There’s a fine line between creating great code and creating understandable code.  In this case, we should opt for the latter, since this is an educational exercise (also considering that you would probably never want to use a binary search tree in JavaScript in practice, but that’s another subject).

So how then should we go about this?  I like the approach borrowed from philosophy that builds on first principles: start out small and gradually build onto your theory.  Likewise, we’ll start with a barely functional binary search tree (BST) and go from there:

var SimpleBinarySearchTree = function () {
	// define our private variables
	var root = null;

	// node constructor
	var node = function () {
		var node = {
			value:  null,
			left:   null,
			right:  null
		};

		return node;
	};

	// create the root node
	root = new node();
	root.left = new node();
	root.right = new node();

	// recursive function that finds the correct place to insert the node
	var insert = function (value, curNode) {
		// if curNode isn't defined, set it to root
		curNode = typeof (curNode) !== 'undefined' ? curNode : root;

		if (curNode.value === null) {
			// empty spot has been found, so insert here!
			curNode.value = value;
			curNode.left  = new node();
			curNode.right = new node();
		} else {
			// still looking for a place to insert
			// if value is less than curNode, go down to the left node, otherwise go down to the right node
			insert (value, value < curNode.value ? curNode.left : curNode.right);
		}
	};

	// display to the console using inorder traversal
	var display = function (curNode) {
		// set default parameter for curNode to root
		curNode = typeof (curNode) !== 'undefined' ? curNode : root;

		if (curNode.value !== null) {
			display (curNode.left);
			console.log (curNode.value);
			display (curNode.right);
		}
	};

	// declare public functions
	return {
		insert: insert,
		display: display
	}
}

// time to test it out!
var bst = new SimpleBinarySearchTree();
bst.insert (5);
bst.insert (1);
bst.insert (10);
bst.insert (3);
bst.insert (9);
bst.insert (2);
bst.display ();

Ok!  Now we’re really getting down to it.

When we create a new SimpleBinarySearchTree(), an empty root node is created (line 17).  Then when we insert a value, there’s a check to see if the root node has a value yet (line 26).  If it doesn’t, then the root note is assigned that value.

When we insert more values after this, we start at the root node and compare it with the new value (line 34).  If the new value is less than the root value, we go down to the left, otherwise if the new value is greater than the root value, we go down to the right.

You will notice that insert() is a recursive function, since it calls itself.  If it hasn’t found where to insert the new value, it goes down to the left or right of curNode as appropriate (see above) and redefines curNode to be that left or right node, repeating the process until it finds an empty node into which to insert the new value.  This is much easier to understand if you have encountered recursion before.  In Nicholas’s version, a while loop is used instead, which is easier to comprehend, but not as compact.  I opted for more compact.

Our display() function is also recursive, and works off the principle of inorder traversal, which means that it first visits a node’s left node, the node itself, then the node’s right node.  With the trick of recursion shown above, we will see all numbers outputted to the console in order.

This is under the assumption your browser has a console.log feature!  If it doesn’t, just replace line 45 with alert(curNode.value);

Ok!  So that’s the bare minimum binary search tree.  We have a function to insert values, and a function to check out and confirm that our output is in fact displayed in order!

At this point the tree is missing some nice functions that would be useful in practice:

-a function to find if a value is currently in the tree

-a function to find and remove a value from the tree

-a function to delete the entire tree

-a function to find the depth of the tree

-a function to find the number of elements in the tree

But these will have to come in another blogpost

In the meantime, checkout these links:

Nicholas Zakas’s original post: Computer science in JavaScript: Binary search tree, Part 1

Edits to Nicholas’s code which removes the root and implements recursion