// stutree.cpp - implementation file for tree.h

#include <iostream>
using namespace std;

// ------------------- Public Gradetree members ----------------------
//
// These can be called from clients.
// Each has a corresponding recursive private member
// 
// -------------------------------------------------------------------

// default constructor
Gradetree::Gradetree ()
{
	root = NULL;
}

// copy constructor - for deep copies
Gradetree::Gradetree (const Gradetree& othergradetree)
{
	root = copytree (othergradetree.root);
}

// destructor
Gradetree::~Gradetree ()
{
	destroytree (root);
}

// overload assignment for deep copies
void Gradetree::operator= (const Gradetree& othergradetree)
{
	root = copytree (othergradetree.root);
}

// visit inorder and display grades
void Gradetree::Inorder ()
{
	Inorder (root);
}

// visit preorder and display grades
void Gradetree::Preorder ()
{
	Preorder (root);
}

// visit postorder and display grades
void Gradetree::Postorder ()
{
	Postorder (root);
}

// display a sideways "picture" of the tree
void Gradetree::TreePicture ()
{
	Treepicture (root, 1);
}

// add a new grade to the tree
void Gradetree::Insert (int newgrade)
{
	Insert (root, newgrade);
}

// delete one occurrence of a grade from the tree
void Gradetree::Delete (int delgrade)
{
        Delete (root, delgrade);
}

// add all of the grades in the tree
int Gradetree::SumGrades()
{
	SumGrades(root);
}

// count the total number of grades
int Gradetree::NumGrades()
{
	NumGrades(root);
}

// return the average
float Gradetree::AvgGrade()
{
	return (float(SumGrades())/NumGrades());
}

// count the number of nodes
int Gradetree::NodeCount()
{
	NodeCount(root);
}

// count the number of leaf nodes
int Gradetree::LeafCount()
{
	LeafCount(root);
}

// count the number of non-leaf nodes 
int Gradetree::NonLeafCount()
{
	NonLeafCount(root);
}

// see if two trees are the same
bool Gradetree::SimilarTrees(Gradetree othertree)
{
	SimilarTrees(root,othertree.root);
}

// return the height of the tree
int Gradetree::Height()
{
	Height(root);
}

// ------------------- Private Gradetree members ----------------------
// 
// These are used by the public members.
// They are necessary to facilitate the recursion.
//
// --------------------------------------------------------------------

// used by copy constructor and operator=
Treenode* Gradetree::copytree (Treenode* t)
{
    Treenode* tmp = NULL;  // for building copy of t

    if (t != NULL)
    {
	tmp = new Treenode;
	tmp->grade = t->grade;
	tmp->count = t->count;
	tmp->left = copytree (t->left);
	tmp->right = copytree (t->right);
    }

    return tmp;
}

// used by destructor
void Gradetree::destroytree (Treenode* t)
{
    if (t != NULL)
    {
	destroytree (t->left);
	destroytree (t->right);
	delete t;
    }
}

void Gradetree::Inorder (Treenode* t)
{
    if (t != NULL)
    {
	Inorder (t->left);
	cout << t->grade << " ";
	Inorder (t->right);
    }
}

void Gradetree::Preorder (Treenode* t)
{
    if (t != NULL)
    {
	cout << t->grade << " ";
	Preorder (t->left);
	Preorder (t->right);
    }
}

void Gradetree::Postorder (Treenode* t)
{
    if (t != NULL)
    {
	Postorder (t->left);
	Postorder (t->right);
	cout << t->grade << " ";
    }
}

void Gradetree::Treepicture (Treenode* t, int level)  // start w/ level == 1
{
    if (t != NULL)
    {
	Treepicture (t->right, level+1);
	for (int i = 1; i < level; i++)  // spacing to "drop" to correct level
		cout << "     ";
	cout << t->grade << "\n";
	Treepicture (t->left, level+1);
    }
}

void Gradetree::Insert (Treenode* &t, int newgrade)
{
    if (t == NULL)  // this is spot where grade belongs
    {
	t = new Treenode;
	t->grade = newgrade;
	t->count = 1;
	t->left = NULL;
	t->right = NULL;
    }
    else  if (newgrade > t->grade)
	Insert (t->right, newgrade);
    else  if (newgrade < t->grade)
	Insert (t->left, newgrade);
    else
	t->count++;
}

void Gradetree::Delete (Treenode* &t, int delgrade) 
{
    if (t == NULL) // grade is not in tree - abort!
        return;
    else if (delgrade < t->grade)
	Delete (t->left, delgrade);
    else if (delgrade > t->grade)
	Delete (t->right, delgrade);
    else  // match found
	if (t->count > 1)  // just subtract if >1 of this grade
	    t->count--;
	else               // need to delete grade node
	{
	    Treenode* temp = t;  // note t is actually parent link to node!
	    if (t->left == NULL && t->right == NULL)  // case 1: delete leaf
	    {
		t = NULL;
		delete temp;
	    }
	    else if (t->left == NULL)  // case 2: no left child, connect to right
	    {
		t = t->right;
		delete temp;
	    }
	    else if (t->right == NULL)  // case 2: no right child, connect to left
	    {
		t = t->left;
		delete temp;
	    }
	    else // yikes - it's a case 3 node!
	    {
		temp = t->left;                // once to left ...
		while (temp->right != NULL)    // ... all the way down right
		    temp = temp->right;    //     to immediate pred.
	        t->grade = temp->grade;        // copy pred to this node
		Delete (t->left, temp->grade); // now delete pred
	    }
	}
}

// SumGrades----------------------
int Gradetree::SumGrades(Treenode* t)
{
	if(t==NULL)
	{
		return 0;
	}
	else
	{
		return ((t->grade*t->count) + SumGrades(t->left) + SumGrades(t->right));
	}
	
}
	
// NumGrades-------------------
int Gradetree::NumGrades(Treenode* t)
{
	if(t==NULL)
	{
		return 0;
	}
	else
		return ((t->count)+ NumGrades(t->left) + NumGrades(t->right));
}

// NodeCount------------------
int Gradetree::NodeCount(Treenode* t)
{
	if(t==NULL)
	{
		return 0;
	}
	else
		return NodeCount(t->left) + NodeCount(t->right) + 1;
}

// LeafCount-------------------
int Gradetree::LeafCount(Treenode* t)
{
	if(t==NULL)
	{
		return 0;
	}
	else if (t->left == NULL && t->right == NULL)
	{
		return 1;
	}
	else
	{
		return LeafCount(t->left) + LeafCount(t->right);
	}	
}


// NonLeafCount---------------
int Gradetree::NonLeafCount(Treenode* t)
{

	if(t==NULL)
	{
		return 0;
	}
	else if(t->left != NULL || t->right != NULL)
	{
		return NonLeafCount(t->left)+ NonLeafCount(t->right) + 1;
	}
	else
	{       
                return NonLeafCount(t->left)+ NonLeafCount(t->right);
        }

}

// SimilarTrees-----------------
bool Gradetree::SimilarTrees(Treenode* t, Treenode* othertree)
{
	if(t == NULL && othertree == NULL)
	{
		return true;
	}
	else if(t == NULL && othertree !=NULL)
	{
		return false;
	}
	else if(t != NULL && othertree == NULL)
	{
		return false;
	}
	else if(t->left == NULL && othertree->left != NULL)
	{	
		return false;
	}
	else if(t->right == NULL && othertree->right !=NULL)
	{
		return false;
	}
	else if(t->left !=NULL && othertree->left == NULL)
	{
		return false;
	}
	else if(t->right != NULL && othertree->right == NULL)
	{
		return false;
	}
	else
		return SimilarTrees(t->left, othertree->left) && SimilarTrees(t->right, othertree->right);

	
}

// Height-------------------------
int Gradetree::Height(Treenode* t)
{
	int height1, height2, maxheight;
	if(t==NULL)
	{
		return -1;
	}
	else 
	{
		height1= Height(t->left);
		height2= Height(t->right);

		if(height1 > height2)
			maxheight = height1 + 1;
		else
			maxheight = height2 + 1;

		return maxheight;
	}
}