#include<iostream>
using namespace std;
template <class T>
class BST;
template <class T>
class node
{
friend class BST<T>;
public:
    node *left;
    T data;
    node * right;


};
template <class T>
class BST
{

    node<T> *root;
public:
    int count;
    node<T>* getroot(){
    return root;}
BST()
{
count=0;
    root=NULL;
}

    int insert(T val)
    {
        node<T>*cur,*prev;
        cur=root;
        prev=NULL;
        while(cur)
        {
            prev=cur;
            if(cur->data==val)
                    return 0;
            else if(val<cur->data)
                cur=cur->left;
            else if (val>cur->data)
                cur=cur->right;
        }
        cur=new node<T>;
        cur->left=cur->right=NULL;
        cur->data=val;
        if(root==NULL)
            root=cur;
        else if(val<prev->data)
                prev->left=cur;
        else
            prev->right=cur;
        return 1;
    }
    void inorder (node<T> *cur)
    {
       if(cur!=NULL)
        {
            inorder(cur->left);
            cout<<cur->data<<"\t";
            inorder(cur->right);
        }
    }
    void countnode (node<T> *cur)
    {
       if(cur!=NULL)
        {
            countnode(cur->left);
            count=count+1;
            countnode(cur->right);
        }
    }
void preorder (node<T> *cur)
    {
       if(cur!=NULL)
        {  cout<<cur->data<<"\t";
            preorder(cur->left);
            preorder(cur->right);
        }
    }

   void  postorder (node<T> *cur);

   int del(T val)
   {

       node<T>*cur,*nx,*suc;
       cur=root;
       nx=NULL;
       suc=NULL;
       while(cur)
       {
           if(val<cur->data)
                cur=cur->left;
           else if(val>cur->data)
                cur=cur->right;
           else
                break;

       }
       if(!cur)
            return 0;
       nx=cur->left;
       while(nx->right)
       {
           suc=nx;
           T d=nx->data;
           nx=nx->right;

       } cur->data=nx->data;
       suc->right=nx->left;
       delete nx;
       return 1;


   }

  int search(node<T> *cur,T value)
  {
      if(cur==NULL)
        return 0;
      if(cur->data ==value)
        return 1;
      else if (value<cur->data)
            {

            int k=  search(cur->left,value);
              return k;
            }
        else   {int k=search(cur->right,value);

            return k;
        }




  }

   int depth(node<T> *cur)
      {

       if(cur==NULL)
            return 0;
        int ld=depth(cur->left);
        int rd=depth(cur->right);

        if(ld>rd)
            return ld+1;
        else
            return rd+1;

   }
};
template <class T>
 void BST<T>:: postorder (node<T> *cur)
    {
       if(cur!=NULL)
        {
            postorder(cur->left);
            postorder(cur->right);
            cout<<cur->data<<"\t";
        }
    }


int main(){

BST <int> t;
t.insert(10);
t.insert(30);
t.insert(4);
t.insert(1);
t.insert(35);
t.insert(40);

cout<<"inorder " ;
t.inorder(t.getroot());
//cout<<endl<<"postordr ";
//t.postorder(t.getroot());
//cout<<endl<<"preordr ";
//t.preorder(t.getroot());
//int r=t.del(4);
//cout<<endl<<r;

//t.inorder(t.getroot());

cout<<endl<<t.depth(t.getroot())<<endl;

cout<<t.search(t.getroot(),35)<<endl;
t.countnode(t.getroot());
cout<<"total nodes"<<t.count;

}