// Binary Search Tree - Implemenation in C++
// Simple program to create a BST of integers and search an element in it 
#include<iostream>
using namespace std;
//Definition of Node for Binary search tree
struct BstNode {
	int data;
	BstNode* left;
	BstNode* right;
};

// Function to create a new Node in heap
BstNode* GetNewNode(int data) {
	BstNode* newNode = new BstNode();
	newNode->data = data;
	newNode->left = newNode->right = NULL;
	return newNode;
}

// To insert data in BST, returns address of root node 
BstNode* Insert(BstNode* root, int data) {
	if (root == NULL) { // empty tree
		root = GetNewNode(data);
	}
	// if data to be inserted is lesser, insert in left subtree. 
	else if (data <= root->data) {
		root->left = Insert(root->left, data);
	}
	// else, insert in right subtree. 
	else {
		root->right = Insert(root->right, data);
	}
	return root;
}
//To search an element in BST, returns true if element is found
bool Search(BstNode* root, int data) {
	if (root == NULL) {
		return false;
	}
	else if (root->data == data) {
		return true;
	}
	else if (data <= root->data) {
		return Search(root->left, data);
	}
	else {
		return Search(root->right, data);
	}
}
void inorder(BstNode* root) {
	if (root != NULL) { // empty tree
		inorder(root->left);
		cout << root->data << "  ";
		inorder(root->right);
	}
}

int maxrek(BstNode*root)
{
	if (root->right == NULL)
		return root->data;
	else
		maxrek(root->right);
}

int minrek(BstNode* root)
{
	if (root->left == NULL)
		return(root->data);
	else
		minrek(root->left);
}

int max(BstNode* root)
{
	BstNode* temp = root;
	while (temp->right != NULL)
		temp = temp->right;
	return(temp->data);
}

int min(BstNode* root)
{
	BstNode* temp = root;
	while (temp->left != NULL)
		temp = temp->left;
	return(temp->data);
}

BstNode* usun(BstNode* root) {
	if (root == NULL)
		return NULL;
	if (root->left == NULL&&root->right == NULL)
	{
		delete root;
		return NULL;
	}

	root->left = usun(root->left);
	root->right = usun(root->right);

	return root;
}



int main() {
	BstNode* root = NULL;  // Creating an empty tree
						   /*Code to test the logic*/
	root = Insert(root, 15);
	root = Insert(root, 10);
	root = Insert(root, 20);
	root = Insert(root, 25);
	root = Insert(root, 8);
	root = Insert(root, 12);
	// Ask user to enter a number.  
	inorder(root);
	cout << endl;
	root = usun(root);
	inorder(root);

	system("pause");
	return 0;
}

//!!!!!!!!!!!!!!!!!!!!!!!
//zrob poprzednik nastepnik i rotacje + 
//implementacje drzewa w klasie i ogarnij drzewo AVL 
//usuwanie dowolnego wezla z drzewa BST!!!!