#include "BST.h"

// Default Constructor
// PRE:
// POST: root set to NULL
BST::BST()
{
	root = nullptr;
}

// De-allocates dynamic memory associated with tree
// PRE:
// POST: Value is inserted, in order, in tree
BST::~BST()
{
	//cout << "... calling destructor ..." << endl;
}

// Insert value in tree maintaining bst property
// PRE:
// PARAM: value = value to be inserted
// POST: Value is inserted, in order, in tree
void BST::insert(int value)
{
	Node* newNode = new Node(value);
	Node* parent = root;
	Node* pos = root;
	bool isLeft = true;
	// Set new root if tree is empty
	if (root == nullptr) {
		root = newNode;
	}
	else {
		// Find parent of new node
		while (pos != nullptr) {
			parent = pos;
			if (value < parent->data) {
				pos = parent->left;
				isLeft = true;
			}
			else {
				pos = parent->right;
				isLeft = false;
			}
		}
		// Insert new node
		if (isLeft) {
			parent->left = newNode;
		}
		else {
			parent->right = newNode;
		}
	}
}

// Searches tree for target
// PRE:
// PARAM: target = value to be found
// POST: Returns true iff target is in tree
bool BST::search(int target)
{
	return false;
}

// Prints contents of tree pre, in, post order
// PRE:
// POST: Prints contents of tree three times:
//       pre order, in order and post order
void BST::print()
{
	cout << "Pre Order" << endl;
	preOrderPrint(root);
	cout << endl << "In Order" << endl;
	inOrderPrint(root);
	cout << endl << "Post Order" << endl;
	postOrderPrint(root);
}

// Performs an in-order traversal of tree
// PRE:
// POST: Prints contents of tree in order
void BST::inOrderPrint(Node* nd)
{

}

// Performs a pre-order traversal of tree
// PRE:
// POST: Prints contents of tree with pre order traversal
void BST::preOrderPrint(Node* nd)
{

}

// Performs an post-order traversal of tree
// PRE:
// POST: Prints contents of tree with post order traversal
void BST::postOrderPrint(Node* nd)
{

}