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

	
	typedef struct Node {
		int data;
		int height;
		struct Node * left;
		struct Node * right;
	} Node;

	typedef struct AVLTree {
		Node * root;
	} AVLTree;

	Node * initNode (int data);
	void insert(AVLTree * tree, int data);
	Node * insertRecursive(Node * current, int data);
	int getHeight(Node * node);
	void updateHeight(Node * node);
	Node * rotateLeft(Node * node) ;
	Node * rotateRight(Node * node);
	void deleteNode(AVLTree * tree, int data);
	Node * deleteRecursive(Node * current, int data);
	Node * getMin(Node * node);
	void printInorder(AVLTree * tree);
	void printInorderRecursive(Node * current);
	void freeTree(Node * root);

	Node * initNode (int data) {
		Node * newNode = malloc(sizeof(Node));
		newNode->data = data;
		newNode->height = 0;
		newNode->left = NULL;
		newNode->right = NULL;

		return newNode;
	}

	void insert(AVLTree * tree, int data) {
		if (!tree) return;
		tree->root = insertRecursive(tree->root, data);
	}

	Node * insertRecursive(Node * current, int data) {
		if (!current) // Reached endpoint where data must be inserted
			return initNode(data); 
		
		if (data == current->data) 
			return current; // If data already exists, return without adding to tree

		// Recursively traverses to left or right through tree to find where data belongs
		if (data < current->data) {
			current->left = insertRecursive(current->left, data);
		}
		else {
			current->right = insertRecursive(current->right, data);
		}

		// Recursively backtracking through tree after insertion beyond this line

		// Update current node's height
		updateHeight(current);

		// Get balance factor
		int balanceFactor = getHeight(current->left) - getHeight(current->right);

		// If |balance factor| > 1 , determine type of rotation required and call rotate
		
		// Left Left case
		if (balanceFactor > 1 && data < current->left->data) {
			return rotateRight(current);
		}

		// Right Right case
		if (balanceFactor < -1 && data > current->right->data) {
			return rotateLeft(current);
		}

		// Left Right case
		if (balanceFactor > 1 && data > current->left->data) {
			current->left = rotateLeft(current->left);
			return rotateRight(current);
		}

		// Right Left case
		if (balanceFactor < -1 && data < current->right->data) {
			current->right = rotateRight(current->right);
			return rotateLeft(current);
		}
		
		return current;
	}

	// Return a given node's height. Returns -1 if node is NULL
	int getHeight(Node * node) {
		if (!node) return -1;
		return node->height;
	}

	// Update node's height to be larger of the two subtree heights + 1
	void updateHeight(Node * node) {
		if (!node) return;
		
		int leftSubtreeHeight = getHeight(node->left);
		int rightSubtreeHeight = getHeight(node->right);
		int maxSubtreeHeight = leftSubtreeHeight > rightSubtreeHeight ?
									leftSubtreeHeight : rightSubtreeHeight;
		node->height = maxSubtreeHeight + 1;
	}

	// Right child becomes new root
	// Original node becomes left child of new root
	// New root's left subtree is transferred to original node's right
	Node * rotateLeft(Node * node) {
		Node * newRoot = node->right;
		Node * movedSubtree = newRoot->left;

		newRoot->left = node;
		node->right = movedSubtree;

		// Update node heights starting with lower of the two modified nodes
		updateHeight(node);
		updateHeight(newRoot);

		return newRoot;
	}

	// Left child becomes new root
	// Original node becomes right child of new root
	// New root's right subtree is transferred to original node's left
	Node * rotateRight(Node * node) {
		Node * newRoot = node->left;
		Node * movedSubtree = newRoot->right;

		newRoot->right = node;
		node->left = movedSubtree;

		// Update node heights starting with lower of the two modified nodes
		updateHeight(node);
		updateHeight(newRoot);

		return newRoot;
	}

	void deleteNode(AVLTree * tree, int data) {
		if (!tree) return;

		tree->root = deleteRecursive(tree->root, data);
	}

	Node * deleteRecursive(Node * current, int data) {
		if (!current) return NULL;

		// Recursively call delete node in the direction of data
		if (data < current->data) {
			current->left = deleteRecursive(current->left, data);
		}
		else if (data > current->data) {
			current->right = deleteRecursive(current->right, data);
		}
		else // data == current->data , so current node is node to be deleted
		{
			// 0 or 1 child
			// Saves a reference to child or NULL. Deletes current node.
			// Returns child or NULL
			if (!current->left || !current->right) {
				Node * temp = current->left ? current->left : current->right;
				free(current);
				return temp;
			}
			else // 2 children
			{
				// Get the leftmost node from the right subtree (successor)
				// Copy data from successor into current node.
				// Delete successor
				Node * successor = getMin(current->right);
				current->data = successor->data;
				current->right = deleteRecursive(current->right, successor->data);
			}
			
		}

		// Update height
		updateHeight(current);

		// Just like during insertion, must rebalance during recursive backtracking
		// Unlike insertion, AVL deletion determines rotation cases
		// using subtree heights, NOT the deleted value.

		// Get balance factor
		int balanceFactor = getHeight(current->left) - getHeight(current->right);

		// If |balance factor| > 1 , determine type of rotation required and call rotate

		// Left heavy subtree 
		// Fix with right rotation
		if (balanceFactor > 1) {
			if (getHeight(current->left->left) >= getHeight(current->left->right)) {
				return rotateRight(current); // Left Left
			} else {
				current->left = rotateLeft(current->left); // Left Right
				return rotateRight(current);
			}
		}

		// Right heavy subtree
		// Fix with left rotation
		if (balanceFactor < -1) {
			if (getHeight(current->right->right) >= getHeight(current->right->left)) {
				return rotateLeft(current); // Right Right
			} else {
				current->right = rotateRight(current->right); // Right Left
				return rotateLeft(current);
			}
		}
		
		return current;
	}

	Node * getMin(Node * node) {
		while (node->left)
			node = node->left;
		return node;
	}

	void printInorder(AVLTree * tree) {
		if (!tree) return;
		printInorderRecursive(tree->root);
		printf("\n");
	}

	void printInorderRecursive(Node * current) {
		if (!current) return;

		printInorderRecursive(current->left);
		printf("%d ", current->data);
		printInorderRecursive(current->right);
	}

	void freeTree(Node * root) {
		if (!root) return;
		freeTree(root->left);
		freeTree(root->right);
		free(root);
	}

	int main() {
		AVLTree * tree = malloc(sizeof(AVLTree));
		tree->root = NULL;

		int data[] = {90, 23, 13, 56, 84, 49, 93, 27, 64, 89, 72, 34, 13, 2, 9, 22, 72, 85, 40, 51};
		int dataCount = 20;

		printf(" Building AVL tree with %d possible nodes...\n\n", dataCount);
		for (int i = 0; i < dataCount; i++) {
			int newData = data[i];
			insert(tree, newData);
		}
		
		printf("Tree successfully built. Duplicates automatically disregarded.\n");
		printf("Printing tree...\n");
		printInorder(tree);

		// The following call will successfully delete the node with data value 90
		printf("\nAttempting to delete 90...\n");
		deleteNode(tree, 90);
		printf("\nTree state after attempted deletion.\n");
		printInorder(tree);

		// The following call will successfully delete the node with data value 49
		printf("\nAttempting to delete 49...\n");
		deleteNode(tree, 49);
		printf("\nTree state after attempted deletion.\n");
		printInorder(tree);

		// The following call attempts to delete 58. Since 58 is not in the tree,
		// the structure remains unchanged. 
		printf("\nAttempting to delete 58...\n");
		deleteNode(tree, 58);
		printf("\nTree state after attempted deletion.\n");
		printInorder(tree);

		freeTree(tree->root);
		free(tree);

		return 0;
	}