#include<iostream>
#include<cassert>
using namespace std;


/**////////////////////////A_CLASS_TEMPLATE_FOR_BST//////////////////////////////
template< class NODETYPE > class Tree;

template< class NODETYPE >
class TreeNode
{
    friend class Tree< NODETYPE >;
public:
    TreeNode( const NODETYPE &d ):leftPtr( 0 ), data( d ), rightPtr( 0 ){ }
    NODETYPE getData() const 
    {
        return data; 
    }
private:
    TreeNode< NODETYPE > *leftPtr;
    NODETYPE data;
    TreeNode< NODETYPE > *rightPtr;
};



template< class NODETYPE >
class Tree{
public:
   Tree();
   void insertNode( const NODETYPE & );
   void preOrderTraversal() const;
   void inOrderTraversal() const;
   void postOrderTraversal() const;
private:
   TreeNode< NODETYPE > *rootPtr;

   void insertNodeHelper(
    TreeNode< NODETYPE > **, const NODETYPE & );
   void preOrderHelper( TreeNode< NODETYPE > * ) const;
   void inOrderHelper( TreeNode< NODETYPE > * ) const;
   void postOrderHelper( TreeNode< NODETYPE > * ) const;
};

template< class NODETYPE >
Tree< NODETYPE >::Tree() { rootPtr = 0; }

template< class NODETYPE >
void Tree< NODETYPE >::insertNode( const NODETYPE &value )
{
insertNodeHelper( &rootPtr, value );
}

template< class NODETYPE >
void Tree< NODETYPE >::insertNodeHelper(TreeNode< NODETYPE > **ptr, const NODETYPE &value )
{
    if( *ptr == 0 )
    {
       *ptr = new TreeNode< NODETYPE >( value );
       assert( *ptr != 0 );
    }
else
   if( value < ( *ptr )->data )
       insertNodeHelper( &( ( *ptr )->leftPtr ), value );
   else
       if( value > ( *ptr )->data )
           insertNodeHelper( &( ( *ptr )->rightPtr ), value );
   else
     cout<< value << " dup" << endl;
} 

template< class NODETYPE >
void Tree< NODETYPE >::preOrderTraversal() const
{
    preOrderHelper( rootPtr ); 
}

template< class NODETYPE >
void Tree< NODETYPE >::preOrderHelper(TreeNode< NODETYPE > *ptr ) const
{
    if( ptr != 0 )
    {
       cout<< ptr->data << ' ';
       preOrderHelper( ptr->leftPtr );
       preOrderHelper( ptr->rightPtr );
    }
}

template< class NODETYPE >
void Tree< NODETYPE >::inOrderTraversal() const
{ 
    inOrderHelper( rootPtr );
}

template< class NODETYPE >
void Tree< NODETYPE >::inOrderHelper( TreeNode< NODETYPE > *ptr ) const
{
if( ptr != 0 )
    {
       inOrderHelper( ptr->leftPtr );
       cout<< ptr->data << ' ';
       inOrderHelper( ptr->rightPtr );
    }
}

template< class NODETYPE >
void Tree<NODETYPE >::postOrderTraversal() const
{
    postOrderHelper( rootPtr );
}

template< class NODETYPE >
void Tree< NODETYPE >::postOrderHelper(    TreeNode< NODETYPE > *ptr ) const
{
    if( ptr != 0 )
    {
       postOrderHelper( ptr->leftPtr );
       postOrderHelper( ptr->rightPtr );
       cout<< ptr->data << ' ';  
    }
}
/**///////////////////////////////END_TEMPLATE/////////////////////////////////

int main()
{
    Tree< int > intTree;
    int intVal;
    
    cout<< "Enter 10 integer values:\n";
    for( int i = 0; i < 10; i++ )
    {
        cin>> intVal;
        intTree.insertNode( intVal );
    }
    
    cout<< "\nPreorder traversal\n";
    intTree.preOrderTraversal();
    
    cout<< "\nInorder traversal\n";
    intTree.inOrderTraversal();
    
    cout<< "\nPostorder traversal\n";
    intTree.postOrderTraversal();
    
    return 0;
}