/*
 * Mark Whitley
 * IT 327 - Data Struct
 * Week 8 Lab 1 - C++ implementation of a binary search tree
 */

#include "bstree.h"
#include <string>
#include <iostream>
using namespace std;

static bool debugging = false;

// ------ binary search node, inner class --------

BinarySearchNode::BinarySearchNode(string data)
{
	// ... set this node's 'data' to the passed 'data' param (Hint: use the
	// 'this' keyword to distinguish class scope from local scope)

	// ... set the left and right children to null (Tip: "chained" assignment)

}

void BinarySearchNode::print()
{
	// ... print the 'data' member to stdout, followed by a space (but _no_
	// newline at the end)

}

// ------ binary search tree class --------

// constructor
BinarySearchTree::BinarySearchTree()
{
	// ... set the 'root' member to null

	// ... set the 'size' member to zero

}

bool BinarySearchTree::is_empty()
{
	// ... replace 'false' with an expression that tests if 'root' is NULL. Do
	// not use an 'if', just use a relational operator.
	return false;
}

int BinarySearchTree::get_size()
{
	// ... modify next line to return the 'size' member of this class
	return -1;
}

void BinarySearchTree::insert(string addme)
{
	// we won't insert a node that already exists
	//
	// ... modify condition: test if a node with 'addme' already exists in the
	// tree. (Hint: call the exists() method below)
	if (false) {
		if (debugging) cout << "\"" << addme << "\" already exists in tree" << endl;
		return;
	}

	// ... call the overloaded insert method (below), passing it a new
	// (anonymous) BinarySearchNode, passing 'addme' to the constructor

	// ... there's one more node in the tree; increment 'size' member

}

void BinarySearchTree::insert(BinarySearchNode * insert_me)
{
	// handle the special case: the node we want to insert is the first node

	// ... modify 'if' condition: test if the tree is empty (Hint:
	// don't re-invent the wheel, use one of the methods you just filled in
	// above). 
	if (false) {
		// ... the tree is empty, so set 'root' to the passed node (insert_me)

		// ... get out of this function

	}


	// iterative approach to finding the magic insertion point

	// ... modify next line: set 'node' to the 'root'
	BinarySearchNode * node = NULL;
	// ... modify while condition: while the node is not null
	while (false) {

		// ... modify condition: test if insert_me's _data_ is less than the
		// current node's _data_ (Hint: if you put (insert_me < node) you did
		// it wrong)
		if (false) {
			// ... modify condition: test if current node's left child is null
			if (false) {
				// ... set the current node's left child to insert_me

				// ... get out of this function

			} else {
				// there is a left child, so we need to descend left

				// ... set 'node' to its left child

			}

		// ... modify condition: test if insert_me's _data_ is greater than
		// the current node's _data_ (Hint: just as before, if you put
		// (insert_me > node) you did it wrong)
		} else if (false) {
			// ... modify condition: test if current node's right child is null
			if (false) {
				// ... set the current node's right child to insert_me

				// ... get out of this function

			} else {
				// there is a right child, so we need to descend right
				// ... set 'node' to its right child

			}
		}
	}
}

bool BinarySearchTree::exists(string findme)
{
	// iterative approach to finding a node in the tree

	// ... modify next line: set node to 'root'
	BinarySearchNode * node = NULL;
	// ... modify while condition: loop while node is not null
	while (false) {
		// what follows is a big multiway if..else if.. statement that
		// traverses the tree, testing for a node with a data member
		// containing 'findme'

		// ... if 'findme' equals the current node's data, return true (can be
		// done in one line)

		// ... else if findme is less than the current node's data, set node
		// to its left child (again, can be done in one line)

		// ... else if findme is greater than the current node's data, set node
		// to its right child (one line, if you want)

		// ... uncomment the next line after you've written the previous three
		//else cout << "BinarySearchNode::exists() - Impossible case!" << endl;
	}

	// made it to here? then we didn't find it
	return false;
}

int BinarySearchTree::get_height()
{

	// ... modify return statement: in place of -1 call overloaded get_height()
	// that takes one parameter, pass it 'root'. (you will return that function's
	// return value)
	return -1;
}

int BinarySearchTree::get_height(BinarySearchNode * node)
{
	// ... special case: if the node we were passed is null, return 0 (one or
	// two lines total)


	max_height = 0; // (reset class' "temp" variable)

	// ... call overloaded get_height() that takes 2 parameters, passing it
	// 'node' and 1 (initial height)


	return max_height;
}

// postorder traversal to find max height
void BinarySearchTree::get_height(BinarySearchNode * node, int height)
{
	if (debugging) cout << "get_height(" << node->data << "), height = " << height << endl;

	// ... modify if condition: test if the passed node has a left child (IOW,
	// it's not null)
	if (false) get_height(node->left, height + 1);

	// ... make a line very similar to the previous, except do it with the
	// right child this time


	// made it to here? then we must be at a leaf, so we will test if this
	// branch is the deepest we've found
	if (height > max_height) {
		max_height = height;
		if (debugging) cout << "  found deeper branch, max_height is now: " << max_height << endl;
	}
}

// entry function to the recursive version
void BinarySearchTree::preorder_print()
{
	cout << " preorder printing: ";
	// ... call the overloaded version of preorder_print(), passing it 'root'

	cout << endl;
}

// preorder: root to leaves (node, left, right)
void BinarySearchTree::preorder_print(BinarySearchNode * node)
{
	// ... call the print() method of the passed node (Hint: arrow operator)
	// (Note: "pre" means first)

	// ... modify the if condiiton: test if the passed node has a left child
	// by testing if it is not NULL
	if (false) preorder_print(node->left);

	// ... make a line very similar to the previous, except do it with the
	// right child this time.

}

// entry function to the recursive version
void BinarySearchTree::postorder_print()
{
	cout << "postorder printing: ";
	// ... call the overloaded version of postorder_print(), passing it 'root'

	cout << endl;
}

// postorder: leaves to root (left, right, node)
void BinarySearchTree::postorder_print(BinarySearchNode * node)
{
	// ... if the passed node has a left child, call postorder_print(),
	// passing it the left child (very similar to preorder_print() above)

	// ... like you just did, but with the right child this time

	// ... call the print() method of the passed node
	// (Note: "post" means last)

}

void BinarySearchTree::inorder_print()
{
	cout << "  inorder printing: ";
	// ... call the overloaded version of inorder_print(), passing it 'root'

	cout << endl;
}

// inorder: "sorted" (left, node, right)
void BinarySearchTree::inorder_print(BinarySearchNode * node)
{
	// ... you get to figure this one out all on your own. look at the note
	// right above the function header (3 lines above). I'll also mention by
	// way of a hint that "in" means "between".

}

void BinarySearchTree::print_tree()
{
	print_subtree(root, 0);
}

void BinarySearchTree::print_subtree(BinarySearchNode * node, int level)
{
    if (node == NULL) return;

	print_subtree(node->right, level + 1);

	for (int k = 0; k < 3 * level; k++) cout << " ";
	node->print(); cout << endl;

	print_subtree(node->left, level + 1);
}

// destructor
BinarySearchTree::~BinarySearchTree()
{
	// ... call the clear() method to delete every node

}

void BinarySearchTree::clear()
{
	// ... if the tree is empty, there's nothing to clear. add an 'if'
	// condition that tests if the tree is empty, if it is, return from this
	// function. (Hint: don't re-invent the wheel, use one of this class'
	// methods) (1 or 2 lines total)

	// ... call delete_subtree() on the 'root' node

	// ... set root to null

	// ... set the size to zero

}

// postorder deletion of nodes in a tree
void BinarySearchTree::delete_subtree(BinarySearchNode * node)
{
	// ... you guys get to figure this one out on your own. hint: we want to
	// do a _postorder_ deletion of the nodes. look at postorder_print() above
	// for where you should start, but there are 2 minor changes: (A) we want
	// to recursively call _this_ function, not postorder_print(), and (B)
	// instead of printing, we will delete the node.

}