#include <iostream>

#include <queue>

using namespace std;

typedef struct node

{

int data;

int height;

struct node *left;

struct node *right;

} node;

int max(int a, int b)

{

return a > b ? a : b;

}

// Returns a new Node

node *createNode(int data)

{

node *nn = new node();

nn->data = data;

nn->height = 0;

nn->left = NULL;

nn->right = NULL;

return nn;

}

// Returns height of tree

int height(node *root)

{

if (root == NULL)

return 0;

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

}

// Returns difference between height of left and right subtree

int getBalance(node *root)

{

return height(root->left) - height(root->right);

}

// Returns Node after Right Rotation

node *rightRotate(node *root)

{

node *t = root->left;

node *u = t->right;

t->right = root;

root->left = u;

return t;

}

// Returns Node after Left Rotation

node *leftRotate(node *root)

{

node *t = root->right;

node *u = t->left;

t->left = root;

root->right = u;

return t;

}

// Returns node with minimum value in the tree

node *minValue(node *root)

{

if (root->left == NULL)

return root;

return minValue(root->left);

}

// Balanced Insertion

node *insert(node *root, int item)

{

node *nn = createNode(item);

if (root == NULL)

return nn;

if (item < root->data)

root->left = insert(root->left, item);

else

root->right = insert(root->right, item);

int b = getBalance(root);

if (b > 1)

{

if (getBalance(root->left) < 0)

root->left = leftRotate(root->left); // Left-Right Case

return rightRotate(root); // Left-Left Case

}

else if (b < -1)

{

if (getBalance(root->right) > 0)

root->right = rightRotate(root->right); // Right-Left Case

return leftRotate(root); // Right-Right Case

}

return root;

}

// Balanced Deletion

node *deleteNode(node *root, int key)

{

if (root == NULL)

return root;

if (key < root->data)

root->left = deleteNode(root->left, key);

else if (key > root->data)

root->right = deleteNode(root->right, key);

else

{

// Node to be deleted is leaf node or have only one Child

if (!root->right)

{

node *temp = root->left;

delete (root);

root = NULL;

return temp;

}

else if (!root->left)

{

node *temp = root->right;

delete (root);

root = NULL;

return temp;

}

// Node to be deleted have both left and right subtrees

node *temp = minValue(root->right);

root->data = temp->data;

root->right = deleteNode(root->right, temp->data);

}

// Balancing Tree after deletion

return root;

}

// LevelOrder (Breadth First Search)

void levelOrder(node *root)

{

queue<node *> q;

q.push(root);

while (!q.empty())

{

root = q.front();

cout << root->data << " ";

q.pop();

if (root->left)

q.push(root->left);

if (root->right)

q.push(root->right);

}

}

int main()

{

// Testing AVL Tree

node *root = NULL;

int i;

for (i = 1; i <= 7; i++)

root = insert(root, i);

cout << "LevelOrder: ";

levelOrder(root);

root = deleteNode(root, 1); // Deleting key with value 1

cout << "\nLevelOrder: ";

levelOrder(root);

root = deleteNode(root, 4); // Deletin key with value 4

cout << "\nLevelOrder: ";

levelOrder(root);

return 0;

}