// verify class for avergae heights of binary search trees
public class verify {

public static void main(String[] args) {
		
	BinarySearchTree tempTree=null;
	int currentNodes=5;	// initial numbre of nodes
	int nTrees=10000;		// number of trees created to get the average height
	
	for(int i=1; i<=10; i++){ // Different number of nodes
		
		int totalHeight=0; // total heights for the nTrees of currentNodes size

		// creating differnt trees with same number of nodes
		for(int j=1; j<=nTrees;j++) { 
			// cteating one empty binary tree 		
			tempTree= new BinarySearchTree(new IntegerComparator()); 
				
			// loop to insert nodes into the empty tree
			for(int k=1; k<=currentNodes;k++){ 

				// creat random key value!!
				int randKey=(int) (Math.random()*currentNodes*100);

				// insert the random key into the tree with null element value	
				tempTree.insertItem(new Integer(randKey), null);
			}
								
			totalHeight+=(treeHeight(tempTree,tempTree.root()));
		}

			System.out.println("Number of Nodes : "+currentNodes+"\tAverage Height = "+((totalHeight/10000.0)-1));
		currentNodes=currentNodes*2;
	}
		
}

// calculating Height of a node at Position r in a Binary Search Tree 
static public int treeHeight(BinarySearchTree t, Position r){
	 // if the node is internal, 
	 //  then its height is 1+ maximum of left or height children
	if(t.isInternal(r)){

		if(treeHeight(t,t.leftChild(r))>treeHeight(t,t.rightChild(r)))
			return 	treeHeight(t,t.leftChild(r))+1;
		else 	return 	treeHeight(t,t.rightChild(r))+1;
	}
	else return 0;	// if the nodes is external, then its height is 0
	
}
	
}