#include "tree-utils.h"

// Exercise 1

template <class T>
void myInsertInBST(Tree<T>* tree, const T& elem) {
	if (elem > tree->data) {
		if (tree->right == nullptr)
			tree->right = new Tree<T>(elem);
		else
			myInsertInBST(tree->right, elem);
	}
	else {
		if (tree->left == nullptr)
			tree->left = new Tree<T>(elem);
		else
			myInsertInBST(tree->left, elem);
	}
}

void ex1() {
	Tree<int>* t = new Tree<int>(8, new Tree<int>(3, new Tree<int>(1), new Tree<int>(6, nullptr, new Tree<int>(7))), new Tree<int>(10, nullptr, new Tree<int>(14, new Tree<int>(13))));
	myInsertInBST(t, 4);
	printTree(t);

	freeTree(t);
}

// Exercise 2

template <class T>
bool myContains(Tree<T>* tree, const T& elem) {
	if (tree == nullptr) return false;
	if (tree->data == elem) return true;
	return myContains(tree->left, elem) || myContains(tree->right, elem);
}

template <class T>
bool myContainsBST(Tree<T>* tree, const T& elem) {
	if (tree == nullptr) return false;
	if (tree->data == elem)
		return true;
	else if (elem < tree->data)
		return myContainsBST(tree->left, elem);
	else
		return myContainsBST(tree->right, elem);
}

void ex2() {
	Tree<int>* t = new Tree<int>(8, new Tree<int>(3, new Tree<int>(1), new Tree<int>(6, new Tree<int>(4), new Tree<int>(7))), new Tree<int>(10, nullptr, new Tree<int>(14, new Tree<int>(13))));
	std::cout << myContains(t, 9) << " " << myContains(t, 4) << std::endl;
	std::cout << myContainsBST(t, 9) << " " << myContainsBST(t, 4) << std::endl;

	freeTree(t);
}

// Exercise 3

template <class T>
void maxRec(Tree<T>* tree, T& max) {
	if (tree == nullptr) return;
	if (tree->data > max) max = tree->data;
	maxRec(tree->left, max);
	maxRec(tree->right, max);
}

template <class T>
T max(Tree<T>* tree) {
	if (tree == nullptr) return T();
	T max = tree->data;
	maxRec(tree, max);
	return max;
}

template <class T>
T maxBST(Tree<T>* tree) {
	if (tree == nullptr) return T();
	while (tree->right != nullptr) tree = tree->right;
	return tree->data;
}

template <class T>
void minRec(Tree<T>* tree, T& max) {
	if (tree == nullptr) return;
	if (tree->data < max) max = tree->data;
	minRec(tree->left, max);
	minRec(tree->right, max);
}

template <class T>
T min(Tree<T>* tree) {
	if (tree == nullptr) return T();
	T max = tree->data;
	minRec(tree, max);
	return max;
}

template <class T>
T minBST(Tree<T>* tree) {
	if (tree == nullptr) return T();
	while (tree->left != nullptr) tree = tree->left;
	return tree->data;
}

void ex3() {
	Tree<int>* t = new Tree<int>(8, new Tree<int>(3, new Tree<int>(1), new Tree<int>(6, new Tree<int>(4), new Tree<int>(7))), new Tree<int>(10, nullptr, new Tree<int>(14, new Tree<int>(13))));
	std::cout << max(t) << " " << maxBST(t) << std::endl;
	std::cout << min(t) << " " << minBST(t) << std::endl;

	freeTree(t);
}

// Exercise 4

template <class T>
void heightRec(Tree<T>* tree, int& result, int current = 0) {
	if (tree == nullptr) return;
	if (current > result) result = current;
	heightRec(tree->left, result, current + 1);
	heightRec(tree->right, result, current + 1);
}

template <class T>
int height(Tree<T>* tree) {
	int result = 0;
	heightRec(tree, result);
	return result;
}

void ex4() {
	Tree<int>* t = new Tree<int>(8, new Tree<int>(3, new Tree<int>(1), new Tree<int>(6, new Tree<int>(4), new Tree<int>(7))), new Tree<int>(10, nullptr, new Tree<int>(14, new Tree<int>(13))));
	std::cout << height(t) << std::endl;

	freeTree(t);
}

// Exercise 5

template <class T>
void inorderTraversal(Tree<T>* tree, void (*todo)(T)) {
	if (tree == nullptr) return;
	inorderTraversal(tree->left, todo);
	todo(tree->data);
	inorderTraversal(tree->right, todo);
}

template <class T>
void print(T elem) {
	std::cout << elem << " ";
}

void ex5() {
	Tree<int>* t = new Tree<int>(8, new Tree<int>(3, new Tree<int>(1), new Tree<int>(6, new Tree<int>(4), new Tree<int>(7))), new Tree<int>(10, nullptr, new Tree<int>(14, new Tree<int>(13))));
	inorderTraversal(t, print); // on a BST, it prints all elements, in ascending order
	std::cout << std::endl;

	freeTree(t);
}

// main

int main() {
	ex5();
}