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

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

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

void insert(node * & t, std::string s)
{ if (t == NULL)
    t = new node(s);
  else if (s < t->data)
    insert(t->left, s);
  else
    insert(t->right, s); }

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

int total_depth(node * t, int depth = 0)
{ if (t == NULL)
    return 0;
  int total = depth;
  total += total_depth(t->left, depth+1);
  total += total_depth(t->right, depth+1);
  return total; }

int deepest_depth(node * t, int depth = 0)
{ if (t == NULL)
    return 0;
  int d1 = depth;
  int d2 = deepest_depth(t->left, depth+1);
  int d3 = deepest_depth(t->right, depth+1);
  return max(d1, max(d2, d3)); }

class tree
{ protected:
    node * root;

  public:
    tree()
    { root = NULL; }

    void insert(std::string s)
    { ::insert(root, s); }

    void print()
    { ::print(root); }

    int total_depth()
    { return ::total_depth(root); }

    int deepest_depth()
    { return ::deepest_depth(root); }
};

std::string random_string()
{ int length = 4 + random() % 6;
  std::string s = "";
  for (int i = 0; i < length; i += 1)
  { char c = 'a' + random() % 26;
    s += c; }
  return s; }

int main(int argc, char * argv[])
{ if (argc < 2)
  { std::cerr << "Enter the tree size on the command line\n";
    exit(1); }
  int N = atoi(argv[1]);
  int number = (1 << N) - 1;
  srandomdev();
  tree t;
  for (int i = 0; i < number; i += 1)
  { std::string s = random_string();
    // std::cout << "adding string " << s << "\n";
    t.insert(s); }
//  t.print();
  std::cout << "average depth = " << t.total_depth()/(double)number << "\n";
  std::cout << "deepest depth = " << t.deepest_depth() << "\n"; }