text: #include <iostream>
  using namespace std;
  
  int sum = 0;
  
  /*———————————————————————————————————————————————————————————————————————————*/
  // AVL Tree
  class Node{
      public:
        int data; // data to be stored in each node
        string info; // data to be stored in each node
        Node* left; // pointer to the left child of that node
        Node* right; // pointer to the right child of that node
        int height; // height of the node
  };
  /*———————————————————————————————————————————————————————————————————————————*/
  // returns the maximum of two numbers
  // used as a helper function to compute the balance factor of a node
  int max(int a, int b){
    return (a > b)? a : b;
  }
  /*———————————————————————————————————————————————————————————————————————————*/
  // returns the height of the node
  int height(Node* n){
    if (n == NULL)
      return 0;
    return n->height;
  }
  /*———————————————————————————————————————————————————————————————————————————*/
  // returns the node with the smallest data element in the AVl Tree
  // does so by returning the left-most node in the whole tree.
  Node* minValueNode(Node* n){
      while (n->left != NULL)
          n = n->left;
      return n;
  }
  /*———————————————————————————————————————————————————————————————————————————*/
  // creates a new node storing the given data (integer and string), and initialises both the child pointers to NULL & height to 1
  Node* newNode(int keydata, string keyinfo){
  
    Node* node = new Node();
    
    node->data = keydata;
    node->info = keyinfo;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;
  
    return(node);
  }
  /*———————————————————————————————————————————————————————————————————————————*/
  Node* rightRotate(Node *x){
    Node* y = x->left;
    Node* T2 = y->right;
  
    // Rotation
    y->right = x;
    x->left = T2;
  
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;
  
    return y;
  }
  /*———————————————————————————————————————————————————————————————————————————*/
  Node* leftRotate(Node *x){
    Node* y = x->right;
    Node* T2 = y->left;
  
    // Rotation
    y->left = x;
    x->right = T2;
  
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;
  
    return y;
  }
  /*———————————————————————————————————————————————————————————————————————————*/
  // returns the balance factor of the node
  int getBalance(Node* N){
    if (N == NULL)
      return 0;
    return height(N->left) - height(N->right);
  }
  /*———————————————————————————————————————————————————————————————————————————*/
  Node* insNode(Node* node, int keydata, string keyinfo){
  
    if (node == NULL)
      return(newNode(keydata, keyinfo));
  
    if (keydata < node->data)
      node->left = insNode(node->left, keydata, keyinfo);
      
    else if (keydata > node->data)
      node->right = insNode(node->right, keydata, keyinfo);
      
    //else 
      //return node;
  
    node->height = 1 + max(height(node->left), height(node->right));
    int balance = getBalance(node);
  
    // Left Left Case
    if (balance > 1 && keydata < node->left->data)
      return rightRotate(node);
  
    // Right Right Case
    if (balance < -1 && keydata > node->right->data)
      return leftRotate(node);
  
    // Left Right Case
    if (balance > 1 && keydata > node->left->data){
      node->left = leftRotate(node->left);
      return rightRotate(node);
    }
  
    // Right Left Case
    if (balance < -1 && keydata < node->right->data){
      node->right = rightRotate(node->right);
      return leftRotate(node);
    }
  
    return node;
  }
  /*———————————————————————————————————————————————————————————————————————————*/
  Node* delNode(Node* root, int key){
      
      //base case
      if (root == NULL){
          return root;
      }
      
      //if key to be deleted is smaller than the root's data, then it lies in the left subtree
      if (key < root->data){
          root->left = delNode(root->left, key);
      }
      
      //if key to be deleted is greater than the root's data, then it lies in the right subtree
      else if (key > root->data){
          root->right = delNode(root->right, key);
      }
      
      //if key is the same as the root's data, then this is the node to be deleted
      else{
          //node has no child
          if (root->left == NULL && root->right == NULL){
              delete root;
              root = NULL;
          }
              
          //node with only one child
          
          //right child
          else if (root->left == NULL){
              Node* temp = root;
              root = root->right;
              delete temp;
          }
          
          //left child
          else if (root->right == NULL){
              Node* temp = root;
              root = root->left;
              delete temp;
          }
          
          //node with two children
          else{
              Node* temp = minValueNode(root->right);
              root->data = temp->data;
              root->right = delNode(root->right, temp->data);
          }
      }
      return root;
  
      root->height = 1 + max(height(root->left), height(root->right));
      int balance = getBalance(root);
   
      // Left Left Case
      if (balance > 1 && getBalance(root->left) >= 0)
          return rightRotate(root);
          
      // Right Right Case
      if (balance < -1 && getBalance(root->right) <= 0)
          return leftRotate(root);
   
      // Left Right Case
      if (balance > 1 && getBalance(root->left) < 0){
          root->left = leftRotate(root->left);
          return rightRotate(root);
      }
   
      // Right Left Case
      if (balance < -1 && getBalance(root->right) > 0){
          root->right = rightRotate(root->right);
          return leftRotate(root);
      }
   
      return root;
  }
  /*———————————————————————————————————————————————————————————————————————————*/
  void getSum(Node* n){ //LDR
      if (n != NULL){
          getSum(n->left);
          sum += n->data;
          getSum(n->right);
      }
  }
  /*———————————————————————————————————————————————————————————————————————————*/
  void inorder(Node* n){ //LDR
      if (n != NULL){
          inorder(n->left);
          cout << n->data << " - ";
          cout << n->info << "\n";
          inorder(n->right);
      }
  }
  /*———————————————————————————————————————————————————————————————————————————*/
  void preorder(Node* n){ //DLR
      if (n != NULL){
          cout << n->data << " - ";
          cout << n->info << "\n";
          preorder(n->left);
          preorder(n->right);
      }
  }
  /*———————————————————————————————————————————————————————————————————————————*/
  void postorder(Node* n){ //LRD
      if (n != NULL){
          postorder(n->left);
          postorder(n->right);
          cout << n->data << " - ";
          cout << n->info << "\n";
      }
  }
  /*———————————————————————————————————————————————————————————————————————————*/
  int CountInternalNodes(Node* root){
      if (root == NULL)
          return 0;
          
      if (root->left == NULL && root->right == NULL)
          return 0;
       
       return 1+CountInternalNodes(root->left)+CountInternalNodes(root->right);
  }
  /*———————————————————————————————————————————————————————————————————————————*/
  int main(){
  
      Node* root = NULL;
      
      int ch, a, b, count;
      string c;
      
      cout << "1 —————> Insert a Node \n";
      cout << "2 —————> Delete a Node \n";
      cout << "3 —————> Traversal : Inorder \n";
      cout << "4 —————> Traversal : Preorder \n";
      cout << "5 —————> Traversal : Postorder \n";
      cout << "6 —————> Number of Internal Nodes \n";
      cout << "7 —————> Sum of Nodes \n";
      cout << "8 —————> Height of the AVL Tree \n";
      cout << "9 —————> Exit \n\n";
    
    
      do{
          cout << "\nEnter your choice : ";
          cin >> ch;
    
          switch(ch){
      
              case (1):
                  cout << "Enter the value to be Inserted to the Tree : ";
                  cin >> a;
                  cout << "Enter it's description : ";
                  cin >> c;
                  root = insNode(root, a, c);
                  break;
          
              case (2):
                  cout << "Enter the element to be Deleted from the Tree : ";
                  cin >> b;
                  delNode(root, b);
                  break;
                  
              case (3):
                  inorder(root);
                  cout << endl;
                  break;
                  
              case (4):
                  preorder(root);
                  cout << endl;
                  break;
                  
              case (5):
                  postorder(root);
                  cout << endl;
                  break;
                  
              case (6):
                  count = CountInternalNodes(root);
                  cout << "Number of Internal Nodes : " << count << endl;
              
              case (7):
                  getSum(root);
                  cout << "Sum of Nodes : " << sum << endl;
                  break;
              
              case (8):
                  cout << "Height of the AVL Tree : " << root->height - 1 << endl;
                  break;
              
              case (9):
                  break;
                  
              default:
                  cout << "Enter a value between 1 and 9";
          }
      }while(ch != 9);
  
      return 0;
  }
  
  
  