Code Blog

This is a continuation of a series introducing data structures in javascript. A binary tree is a tree
based data structure in which each node has at most two child nodes. The child nodes are typically
referred to as the left and right nodes. Nodes with children are called parent nodes. The absolute
first node in the tree is referred to as the root node.

A binary search tree is a binary tree that is organized with the following properties:

– The left subtree of a node contains only nodes with keys that are less than the nodes key.
– The right subtree of a node contains only nodes with keys that are greater than the nodes key.
– Both the left and right subtrees must also be binary trees

With the data inserted into the tree in this manner, searching becomes more effecient than within an array
because traversal of the data structure can logically exclude elements for comparison. Traversing the structure
from the root node, a greater than or less than check will eliminate half of the data to be compared; assuming
that it is a perfectly balanced tree.

Each node in a binary search tree is similar to a doubly linked list in that they contain some data as well
as two pointers to other nodes. The key difference from a doubly linked list is that the nodes relate to
one another.

A javascript implementation of such a node would look like the following:

var node = {
	data: 17,
	left: null,
	right: null
}

The first step in building a binary search tree implementation is to define a custom type with a single property
that represents the root node.

function BinarySearchTree() {
	this.root = null;
}

To insert a value into the tree you must traverse the tree using the rules that are defined earlier in this document.
The one special case is when no root node exists; denoting that the node to be inserted is the root node.

BinarySearchTree.prototype = {
    insert: function(data){
        var node = {
                data: data,
                left: null,
                right: null
            };

        var currentNode;

        if (this.root === null){
            this.root = node;
        } else {
            currentNode = this.root;

            while(true){
                if (data < currentNode.data){
                    if (currentNode.left === null){
                        currentNode.left = node;
                        break;
                    } else {
                        currentNode = currentNode.left;
                    }
                } else if (data > currentNode.data){
                    if (currentNode.right === null){
                        currentNode.right = node;
                        break;
                    } else {
                        currentNode = currentNode.right;
                    }
                } else {
                    break;
                }
            }
        }
    },
};

Removal of a node from a binary search tree is can be a complex operation because the
tree must remain balanced. This means that all values on the left must be less than
all of the values on the right. There are two special cases to consider when removing
a node as well; existence of the node must be checked as well as determination if the
node to be removed is the root node.

When removing a node, the number of children for that node must be taken into consideration
since the operations become slightly different depending on the number. Removing a node with
two children is the most complex.

BinarySearchTree.prototype = {
    remove: function(data){

        var found = false;
        var parentNode = null;
        var currentNode = this.root;
        var childCount;
        var replacementNode;
        var replacementParent;
            
        while(!found && currentNode){
            if (data < currentNode.data){
                parentNode = currentNode;
                currentNode = currentNode.left;
            } else if (value > current.value){
                parentNode = currentNode;
                currentNode = currentNode.right;
            } else {
                found = true;
            }
        }         

        if (found){
            childCount = (current.left !== null ? 1 : 0) + 
                         (current.right !== null ? 1 : 0);

            if (currentNode === this.root){
                switch(childCount){
                    case 0:
                        this.root = null;
                        break;
                    case 1:
                        this.root = (currentNode.right === null ? 
                                      currentNode.left : currentNode.right);
                        break;
                    case 2:
                        replacementNode = this.root.left;

                        while (replacementNode.right !== null){
                            replacementParent = replacementNode;
                            replacementNode = replacementNode.right;
                        }

                        if (replacementParent !== null){
                            replacementParent.right = replacementNode.left;

                            replacementNode.right = this.root.right;
                            replacementNode.left = this.root.left;
                        } else {
                            replacementNode.right = this.root.right;
                        }

                        this.root = replacementNode;
                }        
            } else {
                switch (childCount){
                    case 0:
                        if (currentNode.data < parentNode.data){
                            parent.left = null;
                        } else {
                            parentNode.right = null;
                        }
                        break;
                    case 1:
                        if (currentNode.data < parentNode.data){
                            parentNode.left = (currentNode.left === null ? 
                                           currentNode.right : currentNode.left);
                        } else {
                            parentNode.right = (currentNode.left === null ? 
                                            currentNode.right : currentNode.left);
                        }
                        break;
                    case 2:
                        replacementNode = currentNode.left;
                        replacementParent = currentNode;

                        while(replacementNode.right !== null){
                            replacementParent = replacementNode;
                            replacementNode = replacementNode.right;
                        }

                        replacementParent.right = replacementNode.left;

                        replacementNode.right = currentNode.right;
                        replacementNode.left = currentNode.left;

                        if (currentNode.data < parentNode.data){
                            parentNode.left = replacementNode;
                        } else {
                            parentNode.right = replacementNode;
                        } 
                }
            }
        }
    },
};

A generic method to traverse the array is useful to have for cases where you may want
to convert the values in the tree to an array or a string.

BinarySearchTree.prototype = {
    traverse: function(evaluate){
        function iterate(node){
            if (node){
                if (node.left !== null){
                    iterate(node.left);
                }            

                evaluate.call(this, node);

                if (node.right !== null){
                    iterate(node.right);
                }
            }
        }
        iterate(this.root);
    },
    
    toArray: function(){
        var result = [];

        this.traverse(function(node){
            result.push(node.data);
        });

        return result;
    },

    toString: function(){
        return this.toArray().toString();
    },    
};

Below are some simple usage examples for this implementation of a binary
search tree in javascript.

var bst = new BinarySearchTree();
bst.add(17);
bst.add(11);
bst.add(43);
bst.add(9);
bst.add(65);
bst.remove(43);

document.writeln(bst.toString()); // prints 9 11 17 65

This is a continuation of a series introducing data structures in javascript. A linked list is a
data structure consisting of a group of nodes that represent a sequence. Each element in a linked
list has a data field and a field that points to the the next node in the linked list. A doubly
linked list also includes a field that points to the previous node in the linked list.

The first step in creating a doubly linked list in javascript is to define a custom type. A doubly
linked list should be defined with a length property, a ‘head’ property which points to the first
element in the list, and a ‘tail’ property which points to the last element in the list.

function DoublyLinkedList() {
	this.length = 0;
	this.head = null;
	this.tail = null;
}

Adding an item to the list is simply a matter of updating the ‘tail’ property with the new item and
updating the previous ‘tail’ item to have a ‘next’ value of the new node. If the length of the list
is zero, the ‘head’ and ‘tail’ properties are set to the node that is being added; making it the
first item in the list.

DoublyLinkedList.prototype = {
	add: function(value) {
		var node = {
			value: value,
			next: null,
			previous: null,
		}
		
		if (this.length == 0) {
			this.head = node;
			this.tail = node;
		}
		else {
			this.tail.next = node;
			node.previous = this.tail;
			this.tail = node;
		}
		
		this.length++;
	},
};

To retrieve a value from the list, it requires that you traverse the list to find the node for a
given index. If an index is provided that does not exist in the list, then a null value should be
returned.

DoublyLinkedList.prototype = {
	getNode: function(index) {
		if ( index > this.Length - 1 || index < 0 ) {
			return null;
		}
		
		var node = this.head;
		var i = 0;
		
		while (i++ < index) {
			node = node.next;
		}
		
		return node;
	},
	
	displayNode: function(index) {
		var node = this.getNode(index);
		if (node != null) {
			document.writeln('value = ' + node.value + '<br />');
			document.writeln('previous = ' + (node.previous != null ? node.previous.value : 'null') + '<br />');
			document.writeln('next = ' + (node.next != null ? node.next.value : 'null') + '<br />' );
			return;
		}
		
		alert('invalid index!');
	},
};

Note that displayNode is just a convenience function for the purpose of this demonstration. In any
case, you should check that the previous or next node is not null before attempting to access the
value.

The final core operation of implementing a doubly linked list is providing the ability to remove an
element. Removing an element from the list is a bit tricky because the previous node and next node
will need to have their properties updated. Any remove operation should handle the case where the
element to be removed is the first or last one. In both of these cases, you will need to update the
‘tail’ and ‘head’ property appropriately. Removing all other elements involves a similar lookup that
is done in the getNode() function. The length should also be manually updated.

DoublyLinkedList.prototype = {
	remove: function(index) {
		if ( index > this.Length - 1 || index < 0 ) {
			return null;
		}
		
		var node = this.head;
		var i = 0;
		
		if (index == 0) {
			this.head = node.next;
			
			// check if we removed the only one in the list
			if (this.head == null) {
				this.tail = null;
			}
			else {
				this.head.previous = null;
			}
		}
		else if (index == this.length - 1) {
			node = this.tail;
			this.tail = node.previous;
			this.tail.next = null;
		}
		else {
			while (i++ < index) {
				node = node.next;
			}
			
			node.previous.next = node.next;
			node.next.previous = node.previous;
		}
		
		this.length--;
	},
};

For convenience, the following is the complete implementation with sample usage.

function DoublyLinkedList() {
	this.length = 0;
	this.head = null;
	this.tail = null;
}

DoublyLinkedList.prototype = {
	add: function(value) {
		var node = {
			value: value,
			next: null,
			previous: null,
		}
		
		if (this.length == 0) {
			this.head = node;
			this.tail = node;
		}
		else {
			this.tail.next = node;
			node.previous = this.tail;
			this.tail = node;
		}
		
		this.length++;
	},
	
	getNode: function(index) {
		if ( index > this.Length - 1 || index < 0 ) {
			return null;
		}
		
		var node = this.head;
		var i = 0;
		
		while (i++ < index) {
			node = node.next;
		}
		
		return node;
	},
	
	displayNode: function(index) {
		var node = this.getNode(index);
		if (node != null) {
			document.writeln('value = ' + node.value + '<br />');
			document.writeln('previous = ' + (node.previous != null ? node.previous.value : 'null') + '<br />');
			document.writeln('next = ' + (node.next != null ? node.next.value : 'null') + '<br />' );
			return;
		}
		
		alert('invalid index!');
	},
	
	remove: function(index) {
		if ( index > this.Length - 1 || index < 0 ) {
			return null;
		}
		
		var node = this.head;
		var i = 0;
		
		if (index == 0) {
			this.head = node.next;
			
			// check if we removed the only one in the list
			if (this.head == null) {
				this.tail = null;
			}
			else {
				this.head.previous = null;
			}
		}
		else if (index == this.length - 1) {
			node = this.tail;
			this.tail = node.previous;
			this.tail.next = null;
		}
		else {
			while (i++ < index) {
				node = node.next;
			}
			
			node.previous.next = node.next;
			node.next.previous = node.previous;
		}
		
		this.length--;
	},
};

var list = new DoublyLinkedList();
list.add("zero");
list.add("one");
list.add("two");
list.add("three");

list.displayNode(2); // prints value = two, previous = one, next = 3
list.remove(2);
list.displayNode(2); // prints value = three, previous = one, next = null

This is a continuation of a series introducing data structures in javascript. In the last couple of
posts, the javascript Array was introduced and it is recommended to have an understanding of the
javascript Array before reading this article.

Stack

A stack is a linear data structure and abstract data type in which operations are performed via the
last in, first out (LIFO) methodology. Similar to other programming languages there are two main
methods in javascript used to populate and retrieve data in the stack. These methods are ‘push’
and ‘pop’. The ‘push’ method is used to add an element to the top of stack and the ‘pop’ method is
used to remove the top element from the stack.

In javascript, the Array object is used for a stack implementation. Javascript has a push() and a
pop() method for the Array object which makes the implementation rather simple.

	var stack = new Array();
	stack.push("one");
	stack.push("two");
	stack.push("three");

	document.writeln(stack.pop() + " - stack length:" + stack.length); // prints "three - stack length: 2"
	document.writeln(stack.pop() + " - stack length:" + stack.length); // prints "two - stack length: 1" 
	document.writeln(stack.pop() + " - stack length:" + stack.length); // prints "one - stack length: 0" 

One key point to understand is that when pushing an element to the stack it is adding it to the end
of the Array. This may be counter intuitive since it is commonly referred to as the “top of the stack”.

Another point to understand is that when you use the pop method it removes the last element from the
Array as indicated in the code sample when it prints the Array length.

Queue

A queue is also a linear data structure and abstract data type with one key difference from a stack
being that it uses a first in, first out (FIFO) methodology. Another name for a queue is a buffer.
Typical usage of a queue would be for instances where you have more data to manipulate than you can
handle in a single period of time.

In javascript, the Array object is also used for a queue implementation. The unshift() method is
used to add elements to the beginning of an Array; ensuring that when you use pop() you get the first
element that was added to the Array.

	var queue = [];
	queue.unshift("one");
	queue.unshift("two");
	queue.unshift("three");

	document.writeln(queue.pop() + " - queue length:" + queue.length); // prints "one - queue length: 2"
	document.writeln(queue.pop() + " - queue length:" + queue.length); // prints "two - queue length: 1" 
	document.writeln(queue.pop() + " - queue length:" + queue.length); // prints "three - queue length: 0" 

This is a continuation of a series on data structures in javascript. If you have been following
along, the last post introduced the javascript Array. This week we will take a closer look at some of the
methods available in javascript to manipulate an Array.

Array.concat

Array.concat joins two or more Arrays to create a new Array. Since it creates a new Array, it’s
important to understand that the original Array’s will remain unchanged.

var someArray = [ 1, 2, 3 ];
var anotherArray = [ 4, 5, 6 ];

var combinedArray = someArray.concat(anotherArray);
document.writeln(combinedArray); // prints 1, 2, 3, 4, 5, 6

Array.every

Array.every is a method that accepts a function as an argument. Each element in the Array is passed
to the function and evaluates if a condition is true or false. If all elements return true for the
Array, then the every method will return true. If at least one element returns false, then the
every method will return false.

var someArray = [ 1, 2, 3 ];
var anotherArray = [ 4, 5, 6 ];
var evaluateNum = 6;

var isLessThan = function(value) {
	return value < evaluateNum;
}

document.writeln(someArray.every(isLessThan)); // prints 'true'
document.writeln(anotherArray.every(isLessThan)); // prints 'false'

Array.filter

Array.filter will create a new Array of elements that evaluate to true in the given function. This
method passes the current value, the index, and a pointer to the array to the function.

var someArray = [ 1, 2, 3, 4, 5, 6 ];
var evaluateNum = 4;

var isLessThan = function(value) {
	return value < evaluateNum;
}

document.writeln(someArray.filter(isLessThan)); // prints 1, 2, 3

Array.forEach

Array.forEach passes each element of the Array to a given function. This is all this method does.
There is no return value. It’s simply an alternate to the common for loop and may be useful for
reusing common logic while looping through Array’s.

var someArray = [ 1, 2, 3 ];

var printArray = function(value, index) {
	document.writeln(index +' - '+ value);
}

someArray.forEach(printArray); // prints 0 - 1, 1 - 2, 2 - 3

Array.join

Array.join will output an Array as a string with a given delimiter. It is useful for sending a
string to the server that can be parsed using the delimiter.

var someArray = [ 1, 2, 3 ];
var delimited = someArray.join('-');

document.writeln(delimited); // prints 1-2-3

Array.indexOf

Array.indexOf will search the Array until it finds a match for a give search criteria. Once the
match is found, it will return the index of the matching element. It is important to note that it
will return the first match only. It will return -1 if no matches are found.

var someArray = [ 1, 2, 3, 3, 4, 5 ];

document.writeln(someArray.indexOf(3)); // prints 2
document.writeln(someArray.indexOf(9)); // prints -1

Array.lastIndexOf

Array.lastIndexOf provides the same functionality as Array.indexOf, but searches for a match in
reverse order.

var someArray = [ 1, 2, 3, 3, 4, 5 ];

document.writeln(someArray.lastIndexOf(3)); // prints 3
document.writeln(someArray.lastIndexOf(9)); // prints -1

Array.map

Array.map will return a new array containing values in the Array that are determined by a given
function.

var someArray = [ 1, 2, 3, 4, 5, 6 ];
var evaluateNum = 4;

var isLessThan = function(value) {
	if  (value < evaluateNum) {
		return 1;
	}
	return 0;
}

var newArray = someArray.map(isLessThan);
document.writeln(newArray); // prints 1, 1, 1, 0, 0, 0

Array.reverse

Array.reverse intuitively reverses the order of the Array.

var someArray = [ 1, 2, 3, 4, 5, 6 ];
someArray.reverse();

document.writeln(someArray); // prints 6, 5, 4, 3, 2, 1

These are the most commonly used useful Array methods. In the next post, we will introduce some of
the more advanced methods including methods used for creating stacks and queues.