#include<iostream.h>
#include <stdlib.h>		// for rand()
	
typedef class BStree *Position;

class BStree {
private:
	int key;
	BStree *left, *right;
	void Error(char mesg[]) { cout << mesg; }
	int privDepth();
	bool hasChild();
public:
	BStree(int);		// param. konstruktør
	Position find(int);
	Position findMax();
	Position findMin();
	BStree* ins(int);
	BStree* del(int);
	void printInorder();
	void printPreorder();
//	void printPostorder();
	int depth();
	int max(int,int);
	// void printWidth();
};

void randInsertAndDelete(BStree*, int);

BStree::BStree(int a) {
	key = a;
	left = NULL;
	right = NULL;
}

Position BStree::find(int a) {
	if (this == NULL) return NULL;
	if (a < key) 
		return left->find(a);	// search in left subtree
	if (a > key) 
		return right->find(a);	// search in right subtree
	else
		return this;			// a == key
}

Position BStree::findMax() {
	if (right)
		return right->findMax();
	else
		return this;
}

Position BStree::findMin() {
	if (left)
		return left->findMin();
	else 
		return this;
}

Position BStree::ins(int a) {
	if (this == NULL) {		// this is where to insert
		BStree * newnode = new BStree(a);
		return newnode;
	}
	if (a < key)
		left = left->ins(a);
	else if (a > key)
		right = right->ins(a);
	return this;	// a == key. Kunne f.eks. talt antall
}

Position BStree::del(int a) {
	Position tmpcell;
	if (this == NULL) 
		Error("!");
	else if (a < key) left = left->del(a);
	else if (a > key) right = right->del(a);
	else 	// Found the element to be deleted
		if (right && left) {	// Two children
			// Replace with the smallest in right subtree
			tmpcell = right->findMin();
			key = tmpcell->key;
			right = right->del(key);
		} else {
			// one or zero children
			if (!left)
				tmpcell = right;
			else //if (!right)
				tmpcell = left;
			delete this;
			return tmpcell;
		}
		return this; // ?
}

void BStree::printInorder() {
	if (this == NULL) return;
	left->printInorder();
	cout << key << " ";
	right->printInorder();
}

void BStree::printPreorder() {
	if (this == NULL) return;
	cout << key << " ";
	if ( hasChild() ) cout << ":";
	left->printPreorder();
	right->printPreorder();
}

bool BStree::hasChild() {
	return (left || right);
}

int BStree::depth() {
	return (privDepth() - 1);
}

int BStree::privDepth() {	// returns 1 too many
	if (this == NULL) return 0;
	else 
		return max(left->privDepth(), right->privDepth()) +1;
}

int BStree::max(int a, int b) {
	if (a > b) return a;
	else 
		return b;
}

void main() {
	int ant=1600;
	BStree *p = NULL;
	p = p->ins(4);
	randInsertAndDelete(p, ant);
	p->printInorder();
	cout << endl;
	cout << "Depth with " << ant << " nodes: " << p->depth();
}

void randInsertAndDelete(BStree* tree, int num) {
	if (tree == NULL) return;
	for (int i =0; i<num; i++) {
		tree->ins(rand()%1000);
	//	if (rand()%2)
	//		tree->del(rand()%1000);
	}
}