intervalSearchTree.js

function Node(interval, id){
	this.interval = interval;
	this.value = interval[0];
	this.max = interval[1];
	this.list = [];
	this.left = null;
	this.right = null;
	this.id = id;
}

function BinarySearchTree(){
	this.root = null;
}
BinarySearchTree.prototype.add = function(interval, id){
	var root = this.root;
	if(!root){
		this.root = new Node(interval);
		this.root.max = this.root.interval[1];
		this.root.id = id;
		return;
	}
	var currentNode = root;
	var newNode = new Node(interval, id);
	while(currentNode){
		if (interval[0] === currentNode.value){
			currentNode.list.push({interval:interval, id:id});
			if (newNode.max > currentNode.max){
				currentNode.max = newNode.max;
			}
			break;
		}
		if(interval[0] < currentNode.value){
			if(!currentNode.left){	
				if (newNode.max > currentNode.max){
					currentNode.max = newNode.max;
				}		
				currentNode.left = newNode;
				break;
			}
			else{
				if (newNode.max > currentNode.max){
					currentNode.max = newNode.max;
				}	
				currentNode = currentNode.left;
			}
		} 
		else{
			if(!currentNode.right){
				if (newNode.max > currentNode.max){
					currentNode.max = newNode.max;
				}	
				currentNode.right = newNode;
				break;
			}
			else{
				if (newNode.max > currentNode.max){
					currentNode.max = newNode.max;
				}	
				currentNode = currentNode.right;
			}
		}
	}
}

BinarySearchTree.prototype.remove = function(interval, id){
	console.log("Removing:"+interval,id);
	var found = false;
	var parentNode = null;
	var currentNode = this.root;
	var childCount = 0;
	var replacement = null;
	var replacementParent = null;
	var returnValue = {};
	while(!found && currentNode){
		if (interval[0] < currentNode.value){
			parentNode = currentNode;
			if (!currentNode.left){
				return null;
			}
			currentNode = currentNode.left;
		}
		if (interval[0] > currentNode.value){
			parentNode = currentNode;
			if (!currentNode.right){
				return null;
			}
			currentNode = currentNode.right;
		}
		else{
			if (id === currentNode.id && interval[1] === currentNode.interval[1]){
				found = true;
			}
			else{
				for (var i = (currentNode.list.length-1); i >= 0; i--){
					if (currentNode.list[i].id === id && interval[1] === currentNode.list[i].interval[1]){
						returnValue = {interval:currentNode.list[i].interval, id:currentNode.list[i].id}
						if (i > -1){
							currentNode.list.splice(i, 1);
							return returnValue;
						}
					}
				}
				return null;
			}
		}
	}
	if (found){
		if (currentNode.list.length > 0 ){
			console.log(currentNode.list.length);
			returnValue.interval = currentNode.interval;
			returnValue.id = currentNode.id;
			var tempListIndex = 0;
			currentNode.interval = currentNode.list[tempListIndex].interval;
			currentNode.id = currentNode.list[tempListIndex].id;
			if (tempListIndex > -1){
				currentNode.list.splice(tempListIndex, 1);
			}
			return returnValue;
		}
		if (currentNode === this.root){
			console.log("ROOT");
			if (!currentNode.left && !currentNode.right){
				console.log("ROOT NO CHILDREN");
				returnValue.interval = currentNode.interval;
				returnValue.id = currentNode.id;
				this.root = null;
				return returnValue;
			}
			if (!currentNode.left && currentNode.right){
				console.log("ROOT ONE CHILD");
				returnValue.interval = currentNode.interval;
				returnValue.id = currentNode.id;
				this.root = currentNode.right;
				return returnValue;
			}
			if (!currentNode.right && currentNode.left){
				console.log("ROOT ONE CHILD");
				returnValue.interval = currentNode.interval;
				returnValue.id = currentNode.id;
				this.root = currentNode.left;
				return returnValue;
			}
			else{
				console.log("ROOT TWO CHILDREN");
				returnValue.interval = this.root.interval;
				returnValue.id = this.root.id
				replacement = this.root.left;
				while(replacement.right !== null){
					replacementParent = replacement;
					replacement = replacement.right;
				}
				if (replacementParent !== null){
					replacementParent.right = replacement.left;
					replacement.right = this.root.right;
					replacement.left = this.root.left;
				}
				else{
					replacement.right = this.root.right;
				}
				this.root = replacement;
				return returnValue;
			}
		}
		if (!currentNode.left && !currentNode.right){
			console.log("NODE, NO CHILDREN");
			if (currentNode.value > parentNode.value){
				returnValue.interval = currentNode.interval;
				returnValue.id = currentNode.id
				parentNode.right = null;
				return returnValue;
			}
			else{
				returnValue.interval = currentNode.interval;
				returnValue.id = currentNode.id
				parentNode.left = null;
				return returnValue;
			}
		}
		if (!currentNode.left && currentNode.right){
			console.log("NODE ONE CHILD RIGHT");
			console.log(currentNode, currentNode.right, parentNode);
			returnValue.interval = currentNode.interval;
			returnValue.id = currentNode.id
			parentNode.left = currentNode.right;
			return returnValue;
		}
		if (!currentNode.right && currentNode.left){
			console.log("NODE ONE CHILD LEFT");
			returnValue.interval = currentNode.interval;
			returnValue.id = currentNode.id
			parentNode.right = currentNode.left;
			return returnValue;
		}
		else{
			console.log("NODE TWO CHILDREN");
			returnValue.interval = currentNode.interval;
			returnValue.id = currentNode.id
			replacement = currentNode.left;
			replacementParent = currentNode;
			if (replacement.right === null){
				replacement.right = currentNode.right;
				if (currentNode.value < parentNode.value){
					parentNode.left = replacement;
				}
				else {
					parentNode.right = replacement;
				}
			}
			else {
				while(replacement.right !== null){
					replacementParent = replacement;
					replacement = replacement.right;
				}
				replacementParent.right = replacement.left;
				replacement.right = currentNode.right;
				replacement.left = currentNode.left;
				if (currentNode.value < parentNode.value){
					parentNode.left = replacement;
				}
				else {
					parentNode.right = replacement;
				}			
			}	
			return returnValue;
		}
	}
}
var bst = new BinarySearchTree();

bst.add([4, 6], 1);
bst.add([4, 7], 2);
bst.add([0, 2], 3);
bst.add([2, 4], 4);
bst.add([2, 4], 5);
bst.add([0, 4], 6);
bst.add([6, 9], 7);
bst.add([0, 10], 8);

function checkIntersection(interval, tree){
	var currentNode = tree.root;
	var intersection = {};
	while(currentNode){

		console.log("Searching...", currentNode);
		if (currentNode.list.length > 0){
			for (var i = 0; i < currentNode.list.length; i++){
				if (interval[0] < currentNode.list[i].interval[1] && currentNode.list[i].interval[0] < interval[1]){
					intersection.interval = currentNode.list[i].interval;
					intersection.id = currentNode.list[i].id;
					tree.remove(currentNode.list[i].interval, currentNode.list[i].id);
					return intersection;
				}
			}
		}
		if (interval[0] < currentNode.interval[1] && currentNode.interval[0] < interval[1]){
			console.log("INTERSECTION: "+interval, currentNode.interval);
			intersection.interval = currentNode.interval;
			intersection.id = currentNode.id;
			tree.remove(currentNode.interval, currentNode.id);
			return intersection;
		}
		if (!currentNode.left){
			console.log("NO NODE TO LEFT, GO RIGHT");
			if (!currentNode.right){
				console.log("NO MORE NODES");
				return null;
			}
			console.log(currentNode.right);
			currentNode = currentNode.right;
		}
		else if (currentNode.left.max < interval[0]){
			console.log("LEFT MAX: "+currentNode.left.max+" < "+interval[0]+" GO RIGHT");
			currentNode = currentNode.right;
		}
		else{
			console.log("INTERVAL MAY BE TO LEFT, GO LEFT");
			currentNode = currentNode.left;
		}
	}
}

function checkAllIntersections(interval, tree){
	var intersections = [];
	var flag = true;
	while(flag){
		var temp = checkIntersection(interval, tree);
		if (!temp){
			flag = false;
		}
		else{
			intersections.push(temp);
		}
	}
	for (var i = 0; i < intersections.length; i++){
		tree.add(intersections[i].interval, intersections[i].id);
	}
	return intersections;
}

console.log(checkAllIntersections([2,4], bst));
console.log(bst);
console.log(checkAllIntersections([4,6], bst));