#include <stdio.h>
#include <stdlib.h>

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;
  }
};

typedef Node* Tree;


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

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


//**************************************************
//              PRINTING A TREE
//**************************************************

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

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

//==================================================
//                   PrintTree
//==================================================
// PrintTree(T,N) prints tree T in a readable form.
// It uses indentation to show structure.  For 
// example, tree
//
//                  20                         //
//                /    \                       //
//              10     55                      //
//             /  \      \                     //
//            4   17     75                    //
//               /                             //
//             12                              //
//
// is printed in the following form
//      leaf: 4
//    node: 10
//        leaf: 12
//      node: 17
//        null
//  node: 20
//      null
//    node: 55
//      leaf: 75
//
// Parameter N gives the indentation of the root.
// It is the number of units of space to put in front
// of node: 20 in the example.  Each unit of space is
// two spaces.
//==================================================

void PrintTree(Node* T, int N)
{
  if(T == NULL) {
    indent(N);
    printf("null\n");
  }
  else if(T->left == NULL && T->right == NULL) {
    indent(N);
    printf("leaf: %d\n", T->key);
  }
  else {
    PrintTree(T->left, N+1);
    indent(N);
    printf("node: %d\n", T->key);
    PrintTree(T->right, N+1);
  }
}


//**************************************************
//          COMPUTING AND UPDATING THE HEIGHT
//**************************************************

//==================================================
//                   height
//==================================================
// 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
//==================================================
// 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;
}


//**************************************************
//                 REBALANCING
//**************************************************

//==================================================
//                   Rebalance
//==================================================
// 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);
    }
  }
}


//==================================================
//                   Balanced
//==================================================
// Balanced(T) checks that tree T is height-balanced.
// It returns true if T is height balanced, and false
// if not.
//
// This function is only used for debugging.  It can
// be used to check that the trees that are produced
// are being balanced correctly.
//==================================================

bool Balanced(const Node* T)
{
  if(T == NULL) return true;
  else return 
            abs(height(T->left) - height(T->right)) <= 1
         && Balanced(T->left) 
         && Balanced(T->right);
}


//**************************************************
//                 TREE OPERATIONS
//**************************************************

//==================================================
//                   Lookup
//==================================================
// Lookup(X,T) returns true if X is a member of tree
// T, and false if X is not a member of T.
//==================================================

bool Lookup(int X, const Node* T)
{
  if(T == NULL) return false;
  else if(X == T->key) return true;
  else if(X < T->key) return Lookup(X, T->left);
  else return Lookup(X, T->right);
}