#include <stdlib.h>
#include <iostream>
#include "tree.h"


TreeNode::TreeNode(int& d) {
	leftPtr = NULL;
	rightPtr = NULL;
	data = d;
}

TreeNode* Tree::search(TreeNode* node, int data)
{
	if (node == NULL) return NULL;
	else if (data < node->getData())
		search(node->leftPtr, data);
	else if (data > node->getData())
		search(node->rightPtr, data);
	else
		return node;
}

Tree::Tree() {
	rootPtr = NULL;
}


void Tree::insertNode(int value) {
	insertNodeHelper(&rootPtr, value);
}

void Tree::insertNodeHelper(TreeNode** node, int& value )
{
	// se a sub-árvore estiver vazia, criamos uma
	if (*node == NULL)
		*node = new TreeNode(value);
	// se os dados forem menores que os valores do nó atual
	// colocamos o valor em um node anterior a ele
	else if (value < (*node)->getData()) {
		insertNodeHelper(&((*node)->leftPtr), value);
	}
	else if (value > (*node)->getData()) {
		insertNodeHelper(&((*node)->rightPtr), value);
	}
	else {
		std::cerr << value << " dup" << std::endl;
	}
}


void Tree::traversal(int flag) {
	traversalHelper(rootPtr, flag);
}


void Tree::traversalHelper(TreeNode* node, int order)
{
	if (node != NULL) {
		if (order == ORDER_PREFIX) {
			std::cout << node->getData() << " ";
			traversalHelper(node->leftPtr, ORDER_PREFIX);
			traversalHelper(node->rightPtr, ORDER_PREFIX);
		}
		else if (order == ORDER_NORMAL) {
			traversalHelper(node->leftPtr, ORDER_NORMAL);
			std::cout << node->getData() << " ";
			traversalHelper(node->rightPtr, ORDER_NORMAL);
		}
		else if (order == ORDER_POSTFIX) {
			traversalHelper(node->leftPtr, ORDER_POSTFIX);
			traversalHelper(node->rightPtr, ORDER_POSTFIX);	
			std::cout << node->getData() << " ";
		}
	}
}

void Tree::removeNode(int& data) {
	removeNodeHelper(&rootPtr, data);
}


void Tree::removeNodeHelper(TreeNode** node, int data) {
	if (*node == NULL) return;
	else if (data < (*node)->getData())
		removeNodeHelper(&((*node)->leftPtr), data);
	else if (data > (*node)->getData())
		removeNodeHelper(&((*node).rightPtr), data);
	else if (*node == (*node)->getData()) {
		// HALP
	}
}