#include <stdio.h>
#include <stdlib.h>
#include <limits.h>


typedef struct Node
{
    int key;
    struct Node* left;
    struct Node* right;
    int height;
} BST;


int max(int a, int b)
{
    return a > b ? a : b;
}

int min(int a, int b)
{
    return a < b ? a : b;
}


BST* create()
{
    return NULL;
}

void release(BST* root)
{
    if(root)
    {
        release(root->left);
        release(root->right);

        free(root);
    }
}

int getHeight(BST* root)
{
    if(!root)
    	return -1;
    else
    	return root->height;
}

BST* rightRotation(BST* k2)
{
	printf("\nPerforming right rotation %d\n ", k2->key);

    BST* k1 = k2->left;
    k2->left = k1->right;
    k1->right = k2;
    k2->height = max(getHeight( k2->left), getHeight(k2->right)) + 1;
    k1->height = max(getHeight( k1->left), k2->height) + 1;
    return k1; /* nova raiz */
}


BST* leftRotation(BST* k1)
{
	printf("\nPerforming left rotation %d\n ", k1->key);
    BST* k2 = k1->right;
    k1->right = k2->left;
    k2->left = k1;
    k1->height = max(getHeight(k1->left), getHeight(k1->right)) + 1;
    k2->height = max(getHeight(k2->right), k1->height) + 1;
    return k2;  /* nova raiz */
}


BST* leftRightRotation(BST* k3){
    k3->left = leftRotation( k3->left );
    return rightRotation( k3 );
}


BST* rightLeftRotation(BST* k1)
{
    k1->right = rightRotation( k1->right );
    return leftRotation( k1 );
}

BST* insert(int value, BST* root)
{
    if(!root)
    {
        root = (BST*)malloc(sizeof(BST));
        root->key = value;
        root->left = root->right = NULL;

        root->height = 0;
    }
    else if(value < root->key)
    {
        root->left = insert(value, root->left);

         if(getHeight(root->left) - getHeight(root->right) == 2)
         {
          	if(value < root->left->key)
            {
               	root = rightRotation(root);
            }
            else
            {
            	root = leftRightRotation(root);
            }
        }
    }
    else if(value > root->key)
    {
        root->right = insert(value, root->right);

         if(getHeight(root->right) - getHeight(root->left) == 2)
         {
           if(value > root->right->key)
           {
           		root = leftRotation(root);
           }
           else
           {
           		root = rightLeftRotation(root);
           }
        }
    }

	root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
    return root;
}

// Find a node in a Binary Search Tree
BST* search(int key, BST* root)
{
	if(!root || root->key == key)
		return root;
	else if(key < root->key)
		return search(key, root->left);
	else
		return search(key, root->right);
}






void print(BST* root, int spaces)
{
    if(root)
    {
    	print(root->left, spaces + 3);
    	//printf("%d\t", root->key);
    	 for(int i = 0; i < spaces; i++ )
      		printf(" ");

    	printf("%d\n", root->key);

        print(root->right, spaces + 3);
    }
}

// Q02
BST* copy(BST* root)
{
	if(!root)
		return root;

	BST* node = (BST*)malloc(sizeof(BST));
	node->height = root->height;
	node->key = root->key;

	node->left = copy(root->left);
	node->right = copy(root->right);

	return node;
}


// Q03
BST* mirror(BST* root)
{
	if(!root)
		return root;

	BST* right = mirror(root->right);
	BST* left = mirror(root->left);

	root->left = right;
	root->right = left;

	return root;
}

// Q04
int maximum(BST* root)
{
	if(!root)
		return INT_MIN;

	int key = root->key;
	int left_key = maximum(root->left);
	int right_key = maximum(root->right);

	int number = max(key, left_key);
	number = max(number, right_key);

	return number;
}

// Q05
int minimum(BST* root)
{
	if(!root)
		return INT_MAX;

	int key = root->key;
	int left_key = minimum(root->left);
	int right_key = minimum(root->right);

	int number = min(key, left_key);
	number = min(number, right_key);

	return number;
}

// Q06
int isEqual(BST* t1, BST* t2)
{
	if(!t1 && !t2)
		return 1;

	if(t1 && t2 && t1->key == t2->key)
		return isEqual(t1->left, t2->left) && isEqual(t1->right, t2->right);
	else
		return 0;
}

BST* removeOdds(BST* root)
{
	if(!root)
		return root;

	BST* left = root->left;
	BST* right = root->right;


}



int main(int argv, char* argc[])
{
    BST* root = create();

    root = insert(50, root);
    root = insert(1, root);
    root = insert(64, root);
    root = insert(12, root);
    root = insert(18, root);
    root = insert(66, root);
    root = insert(38, root);
    root = insert(95, root);
    root = insert(58, root);
    root = insert(59, root);

    //BST* copied = copy(root);
    BST* copied = create();
    copied = insert(50, copied);
    copied = insert(1, copied);
    copied = insert(64, copied);

    print(root, 0);

    printf("\n\nCOPIED:\n");

    print(copied, 0);

    printf("\n\nEquals: %d\n\n", isEqual(root, copied));

    printf("\n\nMaximum: %d\n\n", maximum(root));
    printf("\n\nMinimum: %d\n\n", minimum(root));

    printf("Mirror: \n");

    root = mirror(root);

    print(root, 0);

 	release(copied);
    release(root);

    return 0;
}