/* bst.c 
 *
 *    This program 
 */

#include <stdio.h>
#include <sys/types.h>
#include <sys/times.h>

#define		MAX_NODES	20
#define		MAX_ATTEMPT	5
#define		swap(a,b,tmp)	{tmp=a;a=b;b=tmp;}

void Permute( int a[], int first, int last );
void BuildTree( int perm[], int N );

long	sumOfHeights, NFactorial;
int	maxHeight, minHeight;

main()
{
	int	N;
	int	a[MAX_NODES];
	float	avg;

	for( N=0; N < MAX_NODES; N++ )
		a[N] = N;

	NFactorial = 1;

	for( N=1; N <= MAX_ATTEMPT; N++ ){
		NFactorial = NFactorial * N;
		maxHeight = 0;
		minHeight = MAX_ATTEMPT;
		sumOfHeights = 0;
		Permute( a, 0, N );
		avg = (float)sumOfHeights / (float)NFactorial;
		printf( "N = %d\tmax = %d\tmin = %d\tavg = %.3f\n",
			N, maxHeight, minHeight, avg );
	}
}


void Permute( int a[], int first, int last )
{
	int	temp, i;

	if( first == last - 1 ){
		BuildTree( a, last );
	} else {
		for( i=first; i < last; i++ ){
			swap( a[i], a[first], temp );
			Permute( a, first+1, last );
			swap( a[i], a[first], temp );
		}
	}
}

/* In BuildTree(), left[k] and right[k] contain the keys of the
   left and right children of the node whose key is k.  They contain
   -1 ifFor example,
   if a node with key 3 has a left c
   */
void BuildTree( int perm[], int N )
{
	int	i, root, height;
	int	newNode, currentNode;
	int	left[MAX_NODES], right[MAX_NODES], depth[MAX_NODES];
	
     
	root = perm[0];
	left[root] = right[root] = -1;
	depth[root] = 1;
	height = 1;

	for( i=1; i < N; i++ ){
		currentNode = root;
		newNode = perm[i];
		right[newNode] = left[newNode] = -1;
		
		while( currentNode != -1 ){
			if( newNode > currentNode ){
				if( right[currentNode] != -1 )
					currentNode = right[currentNode];
				else {
					right[currentNode] = newNode;
					depth[newNode] = depth[currentNode] + 1;
					currentNode = -1;
				}
			} else {
				if( left[currentNode] != -1 )
					currentNode = left[currentNode];
				else {
					left[currentNode] = newNode;
					depth[newNode] = depth[currentNode] + 1;
					currentNode = -1;
				}
			}
		}
		
		if( depth[newNode] > height )
			height = depth[newNode];
	}
	
	sumOfHeights = sumOfHeights + height;
	if( height > maxHeight )
		maxHeight = height;
	if( height < minHeight ) 
		minHeight = height;
}