include

struct Node { int key; Node* left; Node* right; Node* parent; // Added parent pointer for easier traversal Node(int k, Node* p = nullptr) : key(k), left(nullptr), right(nullptr), parent(p) {} };

Node* createNode(int key, Node* parent = nullptr) { return new Node(key, parent); }

Node* rightRotate(Node* x) { Node* y = x->left; x->left = y->right; if (y->right) y->right->parent = x; y->right = x; y->parent = x->parent; x->parent = y; return y; }

Node* leftRotate(Node* x) { Node* y = x->right; x->right = y->left; if (y->left) y->left->parent = x; y->left = x; y->parent = x->parent; x->parent = y; return y; }

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

if (root->key > key) {
    if (root->left == nullptr)
        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 != nullptr)
            root->left = leftRotate(root->left);
    }

    return (root->left == nullptr) ? root : rightRotate(root);
}
else {
    if (root->right == nullptr)
        return root;

    if (root->right->key > key) {
        root->right->left = splay(root->right->left, key);
        if (root->right->left != nullptr)
            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 == nullptr) ? root : leftRotate(root);
}

}

Node* insert(Node* root, int key) { if (root == nullptr) return createNode(key);

root = splay(root, key);

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

Node* newNode = createNode(key);

if (root->key > key) {
    newNode->right = root;
    newNode->left = root->left;
    if (root->left)
        root->left->parent = newNode;
    root->left = nullptr;
}
else {
    newNode->left = root;
    newNode->right = root->right;
    if (root->right)
        root->right->parent = newNode;
    root->right = nullptr;
}

newNode->parent = nullptr; // New root has no parent
return newNode;

}

void inOrder(Node* root) { if (root) { inOrder(root->left); std::cout << root->key << " "; inOrder(root->right); } }

int main() { Node* root = nullptr;

root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);

std::cout << "Inorder traversal of the splay tree: ";
inOrder(root);
std::cout << std::endl;

return 0;

}