// -----------------------------------------------------------------------
// insertHelper
// Private method that does the actual inserting of a NodeData*;
//    assumes properly built and balanced AVL tree
// Node has:
//    -- pointers members -- data (to Nodedata), left, right (to Node)
//    -- int height member; getHeight returns height member (or -1 if nullptr)
//    -- constructor to do initialization

void AVLTree::insertHelper(Node*& current, Nodedata* x) {
   if (current == nullptr)
      // allocates memory for Nodedata, sets left/right pointers to nullptr
      current = new Node(x, nullptr, nullptr);

   // insert into left subtree
   else if (*x < *current->data) {
      insertHelper(current->left, x);
      if (getheight(current->left) - getheight(current->right) == 2) {
         if (*x < *current->left->data)
            leftLeft(current);
         else
            leftRight(current);
      }
   }

   // insert into right subtree
   else if (*x > *current->data) {
      insertHelper(current->right, x);
      if (getheight(current->right) - getheight(current->left) == 2) {
         if (*x > *current->right->data)
            rightRight(current);
         else
            rightLeft(current);
      }
   }

   // duplicate, do nothing, change as needed
   else
      ;

   current->height = max(getHeight(current->left ),
                         getHeight(current->right) ) + 1;
}

void AVLTree::leftLeft(Node*& k2) {
   Node* k1 = k2->left;
   k2->left = k1->right;
   k1->right = k2;
   k2->height = max( getheight(k2->left), getheight(k2->right) ) + 1;
   k1->height = max( getheight(k1->left), k2->height ) + 1;
   k2 = k1;
}