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

using namespace std;

string randstring()
{ int len = random() % 8 + 4;
  string s = "";
  for (int i = 0; i < len; i += 1)
    s += (char)(random() % 26 + 'a');
  return s; }

struct node
{ string data;
  int height;
  node * left, * right; 
  node(string s)
  { data = s; left = NULL; right = NULL; height = 1; } };

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

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

void insert(node * & t, string s)
{ if (t == NULL)
  { t = new node(s);
    return; }
  else if (s < t->data)
    insert(t->left, s);
  else
    insert(t->right, s);
  t->height = 1 + max(height(t->left), height(t->right)); }

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

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

int worstbalance(node * t)
{ if (t == NULL)
    return 0;
  int res = abs(balance(t));
  res = max(abs(res), abs(worstbalance(t->left)));
  res = max(abs(res), abs(worstbalance(t->right)));
  return res; }

int main(int argc, char * argv[])
{ srandomdev();
  if (argc != 2)
  { cerr << "put size on command line\n";
    exit(1); }
  int n = atol(argv[1]);
  node * tree = NULL;
  for (int i = 0; i < n; i += 1)
    insert(tree, randstring());
  print(tree);
  double d = worstbalance(tree);
  cout << "worst balance = " << d << "\n";
  cout << "\n"; }