#include<iostream>
using namespace std;

class BTree
{
public:
  int key;  //data in the node
  BTree *left;   // Pointer to the left subtree.
  BTree *right;  // Pointer to the right subtree.
  BTree();
  ~BTree();
  void insert(int key);   //insert a new node at a leaf position with the given int data
  void insert(BTree* leaf);  //insert a  given leaf node into the tree
  BTree *search(int key); //return NULL if no node has given int value, or a pointer to the node that has the int value
  void destroy();         //clean up the whole tree
  const void preOrderPrint();   
  const void inOrderPrint();
  const void postOrderPrint();
  BTree* find_Max();
  BTree* find_Min();
  int countNodes();
  int countLeafNodes();
  int find_depth();
};


BTree::BTree(){
  left=NULL;
  right=NULL;
}

void BTree::insert(int key){
  BTree* bt=new BTree;  //new node
  bt->key=key;      //assign key to new node
  insert(bt);
}



void BTree::insert( BTree* leaf){
  if(!(this->key)){
       key=leaf->key;
     }
     else if ( (this->key) >= (leaf->key) ){
       if((this->left != NULL)){
	 (this->left)->insert(leaf);
       }else{
	 this->left=leaf;
       }
     }
     else {
       if(this->right != NULL){
	 (this->right)->insert(leaf);
       }else{
	 this->right=leaf;
       }
     }
}



     
const void BTree::inOrderPrint(){
  if( (left==NULL) && (right==NULL) ){
    if(key){cout<<key<<" ";}
  }
  else {
    if(left)left->inOrderPrint();
    cout<<key<<" ";
    if(right)right->inOrderPrint();
  }
}


const void BTree::preOrderPrint(){
  if( (left==NULL) && (right==NULL) ){
    if(key){cout<<key<<" ";}
  }
  else{
    cout<<key<<" ";
    if(left)left->preOrderPrint();
    if(right)right->preOrderPrint();
  }
}

const void BTree::postOrderPrint(){
  if( (left==NULL) && (right==NULL) ){
    if(key){cout<<key<<" ";}
  }
  else{
    if(left)left->postOrderPrint();
    if(right)right->postOrderPrint();  
    cout<<key<<" ";
  }
}





BTree* BTree::find_Max(){
  if(right == NULL){
    return this;
  }else{
    right->find_Max();
  }
}

BTree* BTree::find_Min(){
  if(left == NULL){
    return this;
  }else{
    left->find_Min();
  }
}

int BTree::countNodes(){
  int l, r;
  if((left==NULL)&&(right==NULL)){
    if(key)return 1; else return 0;
  }
  else{
    if(left)
      l=left->countNodes(); else l=0;
    if(right)
      r=right->countNodes(); else r=0;
    return 1+l+r;
  }
}

int BTree::countLeafNodes(){
  int c=0,l=0,r=0;
  if((left==NULL)&&(right==NULL)){
    if(key) c++;
  }else{
    if(left)
      l=left->countLeafNodes(); 
    if(right)
      r=right->countLeafNodes(); 
  }
  return c+l+r;
}

int BTree::find_depth(){ 
  if(this==NULL)
    return 0;
  else{
    int leftDepth=left->find_depth();
    int rightDepth=right->find_depth();
    if (leftDepth>=rightDepth)
      return 1+leftDepth;
    else
      return 1+rightDepth;
  }
}



int main(){
  BTree* bt=new BTree; 
  bt->insert(12);
  bt->insert(5);
  bt->insert(10);
  bt->insert(21);
  bt->insert(13);
  bt->insert(3);
  bt->insert(15);
  bt->insert(22);
  bt->insert(7);
  cout<<"in-order->\t";bt->inOrderPrint();cout<<endl;
  cout<<"pre-order->\t"; bt->preOrderPrint(); cout<<endl;
  cout<<"post-order->\t"; bt->postOrderPrint(); cout<<endl;
  cout<<endl;
  cout<<"Max Value->"<<bt->find_Max()->key<<endl;
  cout<<"Min Value->"<<bt->find_Min()->key<<endl;
  cout<<"# of Nodes->"<<bt->countNodes()<<endl;
  cout<<"# of Leaf Nodes->"<<bt->countLeafNodes()<<endl;
  cout<<"Depth of the tree->"<<bt->find_depth()<<endl;
}

/*********OUTPUT*************
igraine:~$ ./BTree2
in-order->      3 5 7 10 12 13 15 21 22
pre-order->     12 5 3 10 7 21 13 15 22
post-order->    3 7 10 5 15 13 22 21 12

Max Value->22
Min Value->3
# of Nodes->9
# of Leaf Nodes->4
Depth of the tree->4

***************************/