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

  Node(Node *l, int k, Node* r, int h)
  {
    left   = l;
    right  = r;
    key    = k;
    height = h;
  }
};

//==================================================
// max(a,b) returns the larger of a and b.
//==================================================

int max(int a, int b)
{
  if(a > b) return a;
  else return b;
}

//==================================================
// indent(n) prints 2*n spaces.
//==================================================

void indent(int n)
{
  for(int i = 0; i < n; i++){
    cout<< "  ";
  }
}

//==================================================
// height(T) is the current height of tree T.
//
// Requirement: if T is not null then the height field of *T
// must be up to date.
//==================================================

int height(Node* T)
{
  if(T == NULL) return 0;
  else return T -> height;
}

//==================================================
// UpdateHeight(T) sets the height field of *T to the correct
// value.
//
// Requirements:
//  (1) T must not be null.
//  (2) Each of T's children must either be null or must have
//      a correct height field.
//==================================================

void UpdateHeight(Node*& T)
{
  T -> height = max(height(T -> left), height(T -> right)) + 1;
}

//==================================================
// Rebalance(T) rebalances tree T, making it height balanced.
//
// Requirement:
//   If T is not null then each of T's subtrees must already
//   be balanced, with a correct height field (if nonnull).
//
// Note: It is not required for the height field of *T to be
// correct.  That height field will be set by Rebalance.
//==================================================

void Rebalance(Node*& T)
{
  if(T != NULL){
    int heightleft  = height(T -> left);
    int heightright = height(T -> right);
    if(heightright > heightleft + 1){
      RebalanceLeftwards(T);
    }
    else if(heightleft > heightright + 1){
      RebalanceRightwards(T);
    }
    else{
      UpdateHeight(T);
    }
  }
}