package Matala3;

public class BinarySearchTree {
	// tree root
	private BSTNode root;

	//compare two objects (integer type)


	//compare 2 object as they were integer
	private static int compare(Object o1, Object o2) {
		int ans = 0;
		int n1 = ((Number)o1).intValue();
		int n2 = ((Number)o2).intValue();
		if(n1>n2) ans = 1;
		else if(n1<n2) ans = -1;
		return ans;
	}

	public String getRoot(){
		return root.toString();
	}
	// insert element to the tree
	public void insert(Object elem) {
		root = insert(root, elem);
	}
	BSTNode insert(BSTNode tree, Object elem) {
		if (tree == null) {
			return new BSTNode(elem);
		}
		if (compare(elem, tree.data) < 0) {
			tree.left = insert(tree.left, elem);
			return tree;
		}
		else{
			tree.right = insert(tree.right, elem);
			return tree;
		}
	}

	// search for element elem
	public boolean find(Object elem) {
		return find(root,elem);
	}


	boolean find(BSTNode tree, Object elem) {
		if (tree == null)
			return false;
		if (compare(elem, tree.data) == 0)
			return true;
		if (compare(elem, tree.data) < 0)
			return find(tree.left, elem);
		else
			return find(tree.right, elem);
	}

	// print all tree nodes
	public void print() {
		print(root);
		System.out.println();
	}
	void print(BSTNode tree) {
		if (tree != null) {
			print(tree.left);
			System.out.print(tree.data+",");
			print(tree.right);
		}
	}
	// delete emement elem from the tree
	public void delete(Object elem) {
		root = delete(root, elem);
	}
	BSTNode delete(BSTNode tree, Object elem) {
		if (tree == null)
			return null;
		if (compare(elem, tree.data) == 0) {
			if (tree.left == null)
				return tree.right;
			else if (tree.right == null)
				return tree.left;
			else {
				if (tree.right.left == null) {
					tree.data = tree.right.data;
					tree.right = tree.right.right;
					return tree;
				}
				else {
					tree.data = removeSmallest(tree.right);
					return tree;
				}
			}
		}
		else  if (compare(elem, tree.data) < 0) {
			tree.left = delete(tree.left, elem);
			return tree;
		}
		else {
			tree.right = delete(tree.right, elem);
			return tree;
		}
	}
	//  function  removeSmallest is used from function delete
	//	to remove the smallest element of the tree
	Object removeSmallest(BSTNode tree) {
		if (tree.left.left == null) {
			Object smallest = tree.left.data;
			tree.left = tree.left.right;
			return smallest;
		}
		else {
			return removeSmallest(tree.left);
		}
	}

	public Object minimum(){  	//gives the minimal value of the tree.

		BSTNode   min=minimum(root);
		return  min.data;
	}


	BSTNode minimum(BSTNode tree){

		BSTNode lastNode;

		if(tree.left==null)
			return tree;
		else{

			lastNode= minimum(tree.left);
			return lastNode;
		}
	}

	public Object maximum(){		//gives the maximal value of the tree.

		BSTNode   max=maximum(root);
		return  max.data;
	}


	BSTNode maximum(BSTNode tree){

		BSTNode lastNode;
		if(tree.right==null)
			return tree;

		else{

			lastNode= maximum(tree.right);
			return lastNode;
		}

	}
	public int getSize(){			//gives the number of nodes in the tree.
		if(root!=null ){

			int numberOfNodes=size(root);
			return numberOfNodes+1;
		}		//plus the first node}
		else
			return 0;
	}

	int size(BSTNode tree){

		int num1 = 0, num2=0;

		if( tree.left==null && tree.right==null)  return 0;

		if( tree.left!=null && tree.right!=null){
			num1 =size(tree.right)+1;
			num2=size(tree.left)+1;
		}

		if( tree.left==null && tree.right!=null)
			num1 =size(tree.right)+1;

		if(tree.left!=null && tree.right==null)
			num2=size(tree.left)+1;

		return (num1+num2);
	}


	public Object findNearestSmall(Object elem){


		if(compare(elem, minimum())==0) return minimum();

		if(compare(elem, minimum())>0 &&(compare(elem, maximum())<=0))
			return   findNearestSmall(root,elem).data;
		else{

			System.out.println("THE OBJECT IS NOT IN RANGE!!!");
			return null;
		}
	}

	BSTNode findNearestSmall(BSTNode tree,Object elem){
		BSTNode a = null;

		if(tree.right.left!=null){
			if((compare(tree.data, elem)<=0 && compare(tree.right.data,elem)>=0)
					&& compare(tree.right.left.data,elem)<0){
				return (tree.right.left);
			}
		}

		if((compare(tree.data, elem)>=0 && compare(tree.left.data,elem)<=0))
			return (tree.left);

		if((compare(tree.data, elem)<=0 && compare(tree.right.data,elem)>=0))
			return (tree);

		if(compare(tree.data,elem)<0)
			a=findNearestSmall(tree.right,elem);

		if((compare(tree.data,elem)>0))
			a=findNearestSmall(tree.left,elem);

		return a;
	}


	public Object findNearestGrate(Object elem){


		if(compare(elem, maximum())==0) return maximum();

		if(compare(elem, minimum())>=0 &&(compare(elem, maximum())<0))
			return   findNearestGrate(root,elem).data;
		else{

			System.out.println("THE OBJECT IS NOT IN RANGE!!!");
			return null;
		}
	}


	BSTNode findNearestGrate(BSTNode tree,Object elem){
		BSTNode a = null;


		if(tree.left!=null &&  tree.left.right!=null){

			if((compare(tree.data, elem)>=0 && compare(tree.left.data,elem)<=0)
					&& compare(tree.left.right.data,elem)>0){
				return (tree.left.right);
			}
		}

		if(tree.right.left!=null){
			if((compare(tree.data,elem)<=0 && (compare(tree.right.data, elem)>0) &&
					compare(tree.right.left.data, elem)>0))
				return(tree.right.left);

		}

		if((compare(tree.data, elem)<=0 && compare(tree.right.data,elem)>0))
			return (tree.right);

		if((compare(tree.data, elem)>0 && compare(tree.left.data,elem)<=0))
			return (tree);

		if(compare(tree.data,elem)<0)
			a=findNearestGrate(tree.right,elem);

		if((compare(tree.data,elem)>0))
			a=findNearestGrate(tree.left,elem);

		return a;
	}



	//=======================================

	public class BSTNode {
		public Object data;
		public BSTNode left;
		public BSTNode right;
		BSTNode(Object newdata) {
			data = newdata;
			left = null;
			right = null;
		}
		public String toString(){
			return "data: "+data+" ";
		}
	}
	//====================================
}