#include<iostream>
#include<iomanip>
#include<cmath>

#include"treenode.h"
#include"balance.h"

using namespace std;

void insert(treenode *&root, int entry);
void showtree(treenode *root, int depth);
int levels(treenode *root);
int nodes(treenode *root);
double lg(double m);

int main() {
	treenode *t1=NULL, *t2=NULL, *t3=NULL;
	treenode *b1=NULL, *b2=NULL, *b3=NULL;

	insert(t1, 5);
	insert(t1, 10);
	insert(t1, 1);
	insert(t1, 22);
	insert(t1, 7);
	insert(t1, 18);
	insert(t1, 42);
	insert(t1, 35);
	insert(t1, 44);


	cout << endl << "Tree 1: (pre-balance) - " << levels(t1) << " levels, " << nodes(t1) << " nodes. ";
	cout << "Optimal height is ~ " << lg(nodes(t1)) << " levels." << endl;
	showtree(t1, 0);
	b1=balancetree(t1);
	cout << endl << "Tree 1: (post-balance) - " << levels(b1) << " levels" << endl;
	showtree(b1, 0);

	


	return(0);
}



void insert(treenode *&root, int entry) {
	if(NULL!=root) {
		if(entry>root->data)
			insert(root->right, entry);
		else
			insert(root->left, entry);
	}
	else {
		root=new treenode;
		root->data=entry;
		root->left=NULL;
		root->right=NULL;
	}
}

void showtree(treenode *root, int depth) {
	if(root!=NULL) {
		showtree(root->right, depth+1);
		cout << setw(depth*3) << "";
		cout << root->data << endl;
		showtree(root->left, depth+1);
	}
}
	
int levels(treenode *root) {
	if(NULL!=root) {
		int left=levels(root->left);
		int right=levels(root->right);
		if(left>right)
			return(1+left);
		else
			return(1+right);
	}
	else {
		return(0);
	}
}

int nodes(treenode *root) {
	if(NULL!=root)
		return(1+nodes(root->left)+nodes(root->right));
	else
		return(0);
}
		

double lg(double m) { //log base 2.
	double n=log(m);
	double d=log(2.0);
	return(ceil(n/d));
}