#include <iostream>
#include <cstdlib>

struct node
{ int data;
  int Height;
  node * left, * right;

  int height()
  { if (this == NULL)
      return 0;
    return Height; }

  void calculate_height()
  { Height = 1 + max(left->height(), right->height()); }

  node(int d, node * l = NULL, node * r = NULL)
  { data = d; left = l; right = r;
    calculate_height(); } };


node * add_to_tree(node * ptr, int value)
{ if (ptr == NULL)
    return new node(value);
  if (value < ptr->data)
    ptr->left = add_to_tree(ptr->left, value);
  else
    ptr->right = add_to_tree(ptr->right, value);

  ptr->calculate_height();
  int bal = ptr->left->height() - ptr->right->height();
  cout << "we just inserted " << value << " below " 
       << ptr->data << ", Balance here is " << bal << "\n";
  return ptr; }


void inorder_print(node * ptr)
{ if (ptr == NULL)
    return;
  inorder_print(ptr->left);
  cout << ptr->data << " ";
  inorder_print(ptr->right); }


void main()
{ srandomdev();
  node * tree = NULL;
  for (int i = 0; i < 200; i += 1)
  { int v = random() % 1000;
    cout << "\n------adding " << v << " -----\n";
    tree = add_to_tree(tree, v); }
  cout << "\n";
  inorder_print(tree);
  cout << "\n"; }