#include <iostream>
#include <iomanip>
#include <cstdlib>

using namespace std;

struct node
{ int data;
  node * left, * right;
  int height, balance;
  node(int x)
  { data = x;
    left = NULL;
    right = NULL; } };

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

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

int calcbals(node * n)
{ if (n == NULL)
    return 0;
  int tl = calcbals(n->left);
  int tr = calcbals(n->right);
  int hl = ht(n->left);
  int hr = ht(n->right);
  n->height = max(hl, hr) + 1;
  n->balance = abs(hl - hr);
  return tl + tr + n->balance; }

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

int main()
{ srandomdev();
  cout << "How many numbers: ";
  int N;
  cin >> N;
  node * t = NULL;
  for (int i = 0; i<N; i+=1)
  { int r = random();
    add(r, t); }
//  print(t);
  int tb = calcbals(t);
  cout << "average balance = " << tb/(double)N << "\n"; }