AVL Tree

AVL Tree is a self-balancing BST where for any node - the difference in height of the left and the right subtree can not be more than $1$.

Therefore, the strucwture of the AVL tree node also stores the height for each node. The structure would look like this:

struct Node {  
    int key;  
    Node *left;  
    Node *right;  
    int height;  
}; 

...