/****************************************************
	Ed Yakabosky	CSE 120		Section 002
	This is the third homework program for CSE 120.
	In this program, the user enters an array which
		generates a binary tree.  The maximum path
		of the binary tree is then found.
	input: array of integers.
	output: maximum path.
****************************************************/

#include "MaxTree.h"

/* This function is called to insert an array of integers
	into the appropriate spots of a binary tree.  It is
	placed before the constructor because the constructor
	calls it.  It is recursive with a base case
	of the integer currently being read equaling 0
	and calls itself to the left and right pointers
	of each MaxNode structure, otherwise. */
MaxNode* MaxTree::insert(int input[], int a)
{		
			MaxNode* newNode = new MaxNode;
			newNode -> value = input[a];
		
			if (input[a] == 0)
			{
				newNode -> left = NULL;
				newNode -> right = NULL;
			}
			else
			{
				newNode -> left = insert(input, (2 * a) + 1);
				newNode -> right = insert(input, (2 * a) + 2);
			}

			return newNode;
}

// Constructor with recursive function.
MaxTree::MaxTree(int input[])
{
	RootNode  = insert(input, 0);
}

/* Calls recursive function and used to calculate optimal path
   through binary tree */
int MaxTree::getMaxValue()
{
	return CalculateMax(0, RootNode);
}

/* This function calculates the maximum-value path through the binary
	tree.  It is a recursive function with a base case of the value
	currently being read equaling 0.  Until then, the left
	and right paths of each pointer are analyzed until the best
	path is found, and these values are totalled. */
int MaxTree::CalculateMax(int maximum, MaxNode* current)
{
	if (current -> value == 0)
	{
		return maximum;
	}
	else 
	{
		if (CalculateMax(maximum, current -> left) > CalculateMax(maximum, current -> right))
		{
			maximum+= CalculateMax(current -> value, current -> left);
		}
		else
		{
			maximum+= CalculateMax(current -> value, current -> right);
		}
	}
}

/* This function is used to deallocate memory.  It
	is recursive with a base case of the value being
	analyzed to equal 0.  Otherwise, it calls itself
	to the left and right pointers of each MaxNode structure
	and deletes these spaces. */
void MaxTree::erase(MaxNode* &current)
{
	if (current -> value == 0)
	{
		delete current;
	}
	else
	{
		erase(current -> left);
		erase(current -> right);\
		delete current;
	}
}

// Destructor.
MaxTree::~MaxTree()
{
	erase(RootNode);
}