#include  < iostream >
using   namespace  std;

template  < class  T >
struct  BSTreeNode
{
    T info;
    BSTreeNode  * ls;
    BSTreeNode  * rs;
} ;

template  < class  T >
class  BSTree
{
public :
    BSTree();
     bool  insert(T key);
     bool  find(T key);
     void  travel();
     int  size();
private :
     bool  insert_inner(BSTreeNode < T >   *& root, BSTreeNode < T >   * p);
     bool  find_inner(BSTreeNode < T >   * root, T key);
     void  travel_inner(BSTreeNode < T >   * root);
    BSTreeNode < T >   * root;
     int  _size;
} ;

template  < class  T >
BSTree < T > ::BSTree()
{
    root  =  NULL;
    _size  =   0 ;
}

template  < class  T >
bool  BSTree < T > ::insert(T key)
{
    BSTreeNode < T >   * p  =   new  BSTreeNode < T > ;
    p -> info  =  key;
    p -> ls  =  NULL;
    p -> rs  =  NULL;
     if  (insert_inner(root, p))
         return   true ;
     else
         return   false ;
}

template  < class  T >
bool  BSTree < T > ::insert_inner(BSTreeNode < T >   *& root, BSTreeNode < T >   * p)
{
     if  (root  ==  NULL)
     {
        root  =  p;
        _size ++ ;
         return   true ;
    }

     if  (root -> info  ==  p -> info)
         return   false ;

     if  (p -> info  <  root -> info)
        insert_inner(root -> ls, p);
     else
        insert_inner(root -> rs, p);
}

template  < class  T >
bool  BSTree < T > ::find(T key)
{
     if  (find_inner(root, key))
         return   true ;
     else
         return   false ;
}

template  < class  T >
bool  BSTree < T > ::find_inner(BSTreeNode < T >   * root, T key)
{
     if  (root  ==  NULL)
         return   false ;

     if  (root -> info  ==  key)
         return   true ;

     if  (key  <  root -> info)
        find_inner(root -> ls, key);
     else
        find_inner(root -> rs, key);
}

template  < class  T >
int  BSTree < T > ::size()
{
     return  _size;
}

template  < class  T >
void  BSTree < T > ::travel()
{
    travel_inner(root);
}

template  < class  T >
void  BSTree < T > ::travel_inner(BSTreeNode < T >   * root)
{
     if  (root  ==  NULL)  return  ;
    travel_inner(root -> ls);
    cout  <<  root -> info  <<  endl;
    travel_inner(root -> rs);
}


int  main()
{
    BSTree < int >  bst;
     int  a[]  =   { 3 ,  2 ,  5 ,  1 ,  4 } ;
     for  ( int  i = 0 ; i < sizeof (a) / sizeof ( int ); i ++ )
        bst.insert(a[i]);
    bst.travel();
     return   0 ;
}