template<typename T>
class Node
{
public:
    T key;
    Node<T>* left;
    Node<T>* right;
    int height;
};

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

template<typename T>
int height(Node<T>* N)
{
    if (N == nullptr)
    {
        return 0;
    }
    return N->height;
}

template<typename T>
Node<T>* newNode(T key)
{
    Node<T>* node = new Node<T>();
    node->key = key;
    node->left = nullptr;
    node->right = nullptr;
    node->height = 1;
    return(node);
}

template<typename T>
Node<T>* rightRotate(Node<T>* root)
{
    Node<T>* newRoot = root->left;
    Node<T>* newRoot2 = newRoot->right;
    newRoot->right = root;
    root->left = newRoot2;
    root->height = max(height(root->left), height(root->right)) + 1;
    newRoot->height = max(height(newRoot->left), height(newRoot->right)) + 1;
    return newRoot;
}

template<typename T>
Node<T>* leftRotate(Node<T>* root)
{
    Node<T>* newRoot = root->right;
    Node<T>* newRoot2 = newRoot->left;
    newRoot->left = root;
    root->right = newRoot2;
    root->height = max(height(root->left), height(root->right)) + 1;
    newRoot->height = max(height(newRoot->left), height(newRoot->right)) + 1;

    return newRoot;
}

template<typename T>
int getBalance(Node<T>* N)
{
    if (N == nullptr)
    {
        return 0;
    }
    return height(N->left) - height(N->right);
}

template<typename T>
Node<T>* insert(Node<T>* node, int key)
{
    if (node == NULL)
    {
        return(newNode(key));
    }
    if (key < node->key)
    {
        node->left = insert(node->left, key);
    }
    else if (key > node->key)
    {
        node->right = insert(node->right, key);
    }
    else
    {
        return node;
    }
    node->height = 1 + max(height(node->left), height(node->right));

    int balance = getBalance(node);

    if (balance > 1 && key < node->left->key)
    {
        return rightRotate(node);
    }
    if (balance < -1 && key > node->right->key)
    {
        return leftRotate(node);
    }
    if (balance > 1 && key > node->left->key)
    {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    if (balance < -1 && key < node->right->key)
    {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
    return node;
}