I need to create an AVL tree in C++. The function must be of return type node* (will return the root node).

Node should be defined as:

struct node { int val; //value struct node* left; //left child struct node* right; //right child int ht; //height of the node } node; 

Say I am given a pointer to the root of an AVL tree. I need to insert a value into this tree and perform the necessary rotations to ensure that it remains balanced. Please explain logic and add helpful comments if you can :) I am very intereseted in this.

node * insert(node * root,int val) {

}