#include <iostream>

/* 
Here, we added an evil gloabl variable called "howdeep". It
is used to keep track of what level of the tree we are looking
at. Every time print_show_shape is called to follow a pointer
deeper into the tree, howdeep is incremented, and every time
print_show_shape finishes, howdeep is decremented.

Remember the little trick in main() with argc and argv. Now
the program doesn't specifically say to generate 7 random
numbers, you say so on the command line when running it, like

     a.out 7
or
     a.out 100
or whatever
*/

struct node
{ int data;
  node * left, * right;
  node(int i)
  { data=i; left=NULL; right=NULL; } };

struct tree
{ node * root;
  tree()
  { root=NULL; }

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

  void add(int ni)
  { add(ni, root); }

  void print(node * p)
  { if (p==NULL)
      cout << " .";
    else
    { print(p->left);
      cout << " " << p->data;
      print(p->right); } }

  void print()
  { print(root);
    cout << "\n"; }

  int howdeep;

  void print_show_shape(node * p)
  { howdeep+=1;
    if (p!=NULL)
    { print_show_shape(p->left);
      cout << p->data << " at depth " << howdeep << "\n";
      print_show_shape(p->right); }
    howdeep-=1; }

  void print_show_shape()
  { howdeep=0;
    print_show_shape(root);
    cout << "\n"; }

};

void main(int argc, char * argv[])
{ tree T;
  int num = atol(argv[1]);
  srandomdev();
  for (int i=0; i<num; i+=1)
  { int n = random() % 100;
    cout << " " << n;
    T.add(n); }
  cout << "\n";
  T.print();
  T.print_show_shape(); }