Treaps - Insertion

TreapsInsertion.cpp

// base case
if (root == nullptr)
{
  root = new TreapNode(data);
  return;
}

// if given data is less than the root node, insert in the left subtree
// else insert in the right subtree
if (data < root->data)
{
  insertNode(root->left, data);

  // rotate right if heap property is violated
  if (root->left != nullptr && root->left->priority > root->priority)
    rotateRight(root);
}
else
{
  insertNode(root->right, data);

  // rotate left if heap property is violated
  if (root->right != nullptr && root->right->priority > root->priority)
    rotateLeft(root);
}