#include <string>
#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

struct node
{ string data;
  node * left, * right;

  node(string s)
  { data = s;
    left = NULL;
    right = NULL; }

  int totaldepth(int depth = 1)
  { if (this == NULL)
      return 0;
    int total = left->totaldepth(depth+1);
    total += depth;
    total += right->totaldepth(depth+1);
    return total; }

  int worstdepth(int depth = 1)
  { if (this == NULL)
      return 0;
    int worstL = left->worstdepth(depth+1);
    int worstH = depth;
    int worstR= right->worstdepth(depth+1);
    return max(worstL, max(worstH, worstR)); }
};


class tree
{ protected:
    node * root;

  public:
    tree()
    { root = NULL; }

    void insert(string x)
    { if (root == NULL)
      { root = new node(x);
        return; }
      node * ptr = root, * prev = NULL;
      while (true)
      { if (x < ptr->data)
        { prev = ptr;
          ptr = ptr->left;
          if (ptr == NULL)
          { prev->left = new node(x);
            break; } }
        else
        { prev = ptr;
          ptr = ptr->right; 
          if (ptr == NULL)
          { prev->right = new node(x);
            break; } } } }

    int totaldepth()
    { return root->totaldepth(); }

    int worstdepth()
    { return root->worstdepth(); }
};

int random_in_range(int a, int b)
{ return a + random() % (b - a); }

string randomstring()
{ int len = random_in_range(3, 7);
  string s = "";
  for (int i = 0; i < len; i += 1)
    s += (char)random_in_range('A', 'Z');
  return s; }

int main(int argc, char * argv[])
{ srandomdev();
  if (argc != 2)
  { cerr << "Give me a number!\n";
    exit(1); }
  int N = atoi(argv[1]);
  tree T;

  for (int i = 0; i < N; i += 1)
  { string s = randomstring();
    T.insert(s); }
  double log2nm1 = log((double)N)/log(2.0) - 1;
  double avgdept = T.totaldepth()/(double)N;
  cout << "average depth = " << avgdept  << "\n";
  cout << "              = " << avgdept/log2nm1 << " x (log2N)-1\n";
  cout << "worst depth = " << T.worstdepth() << "\n"; }