#include <iostream>
#include <iomanip>

using namespace std;

struct node
{ node * left, * right;
  int data, height, balance;

  node(int d)
  { data = d; left = NULL; right = NULL; } };

node * add(node * t, int d)
{ if (t == NULL)
    return new node(d);
  if (d < t->data)
    t->left = add(t->left, d);
  else
    t->right = add(t->right, d);
  return t; }

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

int balance(node * t)
{ if (t == NULL)
    return 0;
  else
    return t->balance; }

void process(node * t)
{ if (t == NULL)
    return;
  process(t->left);
  process(t->right);
  t->height = max(height(t->left), height(t->right)) + 1;
  t->balance = height(t->left) - height(t->right); }

int worst_balance(node * t)
{ if (t == NULL)
    return 0;
  int L = worst_balance(t->left);
  int R = worst_balance(t->right);
  int U = balance(t);
  if (abs(L) > abs(R) && abs(L) > abs(U))
    return L;
  if (abs(R) > abs(L) && abs(R) > abs(U))
    return R;
  return U; }

void print(node * t, int depth = 0)
{ if (t == NULL)
    return;
  print(t->left, depth + 1);
  cout << setw(depth * 2) << "" << t->data << "\n";
  print(t->right, depth + 1); }

int main(int argc, char * argv[])
{ int N = (1 << atoi(argv[1])) - 1;
  node * T = NULL;
  srandomdev();
  for (int i = 0; i < N; i += 1)
    T = add(T, random() % 10000);
  process(T);
  cout << "Height = " << height(T) << "\n";
  cout << "Balance of root = " << balance(T) << "\n";
  cout << "Worst balance = " << worst_balance(T) << "\n"; }