Splay Tree

#include <iostream>
#include <queue>

using  namespace std;

struct node {
    int key;
    node* left, * right;
};

node* newNode(int);
node* rightRotation(node*);
node* leftRotation(node*);
node* splay(node*, int);
node* insert(node*, int);
void levelorder(node*);
node* Delete(int, node*);
node* Search(int, node*);

int main() {
    node* root = NULL;
    root = insert(root, 100);       //inserts nodes
    root = insert(root, 50);
    root = insert(root, 200);
    root = insert(root, 40);
    root = insert(root, 60);
    int del, serch;

    cout << " Splay tree in levelorder: ";
    levelorder(root);

    cout << "\n Enter a value to be deleted: ";
    cin >> del;

    cout << " Splay tree after delete: ";
    Delete(del, root);
    levelorder(root);

    cout << "\n Enter value to be searched: ";
    cin >> serch;

    cout << " Splay tree after rotation search: ";
    Search(serch, root);
    levelorder(root);

    return 0;
}

node* newNode(int key)
{
    node* temp = new node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
}

node* rightRotate(node* x)
{
    node* y = x->left;
    x->left = y->right;
    y->right = x;
    return y;
}

node* leftRotate(node* x)
{
    node* y = x->right;
    x->right = y->left;
    y->left = x;
    return y;
}

node* splay(node* root, int key)
{
    if (root == NULL || root->key == key)
        return root;

    if (root->key > key) {
        if (root->left == NULL)
            return root;
        if (root->left->key > key) {
            root->left->left = splay(root->left->left, key);
            root = rightRotate(root);
        }
        else if (root->left->key < key) {
            root->left->right
                = splay(root->left->right, key);
            if (root->left->right != NULL)
                root->left = leftRotate(root->left);
        }
        return (root->left == NULL) ? root
            : rightRotate(root);
    }
    else {
        if (root->right == NULL)
            return root;
        if (root->right->key > key) {
            root->right->left
                = splay(root->right->left, key);
            if (root->right->left != NULL)
                root->right = rightRotate(root->right);
        }
        else if (root->right->key < key) {
            root->right->right
                = splay(root->right->right, key);
            root = leftRotate(root);
        }
        return (root->right == NULL) ? root
            : leftRotate(root);
    }
}

node* insert(node* root, int key)
{
    if (root == NULL)
        return newNode(key);

    root = splay(root, key);

    if (root->key == key)
        return root;

    node* temp = newNode(key);
    if (root->key > key) {
        temp->right = root;
        temp->left = root->left;
        root->left = NULL;
    }
    else {
        temp->left = root;
        temp->right = root->right;
        root->right = NULL;
    }
    return temp;
}

void levelorder(node* root) {
    queue<node*> q;

    q.push(root);

    while (!q.empty()) {
        node* nodea = q.front();

        cout << nodea->key << ' ';

        q.pop();

        if (nodea->left != NULL) {
            q.push(nodea->left);
        }
        if (nodea->right != NULL) {    //for some reason, compiler skips this if its on "else if" condition
            q.push(nodea->right);
        }
    }
}

node* Delete(int key, node* root)       //delete function
{
    node* temp;
    if (!root)
        return NULL;
    root = splay(root, key);
    if (key != root->key)
        return root;
    else {
        if (!root->left) {
            temp = root;
            root = root->right;
        }
        else {
            temp = root;

            root = splay(root->left, key);
            root->right = temp->right;
        }
        free(temp);
        return root;
    }
}

node* Search(int key, node* root)       //search function uses splay function but with differnt key value
{
    return splay(root, key);
}