Binary Search Tree

binary-search-tree.js

var Node = function (value) {
	this.value = value;
	this.left = null;
	this.right = null;
};

var BinarySearchTree = function() {
	this._root = null;
};

BinarySearchTree.prototype.isEmpty = function() {
	return this._root === null;
};

BinarySearchTree.prototype.insert = function (value) {
	var node = new Node(value);

	if (this.isEmpty()) {
		this._root = node;
		return;
	}

	var current = this._root;
	
	while (current) {
		if (node.value > current.value) {
			// insert to right
			if (current.right === null) {
				current.right = node;
				break;
			} else {
				current = current.right;
			}
		} else if (node.value < current.value) {
			// insert to left
			if (current.left === null) {
				current.left = node;
				break;
			} else {
				current = current.left;
			}
		} else {
			// ignore duplicates
			break;
		}
	}
};

BinarySearchTree.prototype.traverse = function () {
	this._dump_inorder(this._root);
}

BinarySearchTree.prototype._dump_inorder = function (node) {
	if (node.left !== null) {
		this._dump_inorder(node.left);
	}
	console.log(node);
	if (node.right !== null) {
		this._dump_inorder(node.right);
	}
}

BinarySearchTree.prototype.maximum = function () {
	var current = this._root;
	
	while (current) {
		if (current.right === null) {
			return current;
		}

		current = current.right;
	}
};

BinarySearchTree.prototype.height = function () {
	return this._calculate_height(this._root);
};

BinarySearchTree.prototype._calculate_height = function (node) {
	if (node === null) {
		return 0;
	}

	var left_height = this._calculate_height(node.left);
	var right_height = this._calculate_height(node.right);

	return Math.max(left_height, right_height) + 1;
}

BinarySearchTree.prototype.this._common_ancestor = function (node, n1, n2) {
	if (node === null) {
		return;
	}

	if (node.value < n1 && node.value < n2) {
		return this._common_ancestor(node.left, n1, n2);
	} else if (node.value > n1 && node.value > n2) {
		return this._common_ancestor(node.right, n1, n2);
	} else {
		return node;
	}
}

var tree = new BinarySearchTree();
tree.insert(12);
tree.insert(20);
tree.insert(4);
tree.insert(21);
tree.insert(9);
tree.insert(25);
tree.insert(14);

console.log("/////// inorder traversal ///////");
tree.traverse();

console.log("/////// maximum valued node ///////");
console.log(tree.maximum());

console.log("/////// tree height ///////");
console.log(tree.height());