template < typename elemType >
inline void BinaryTree< elemType >::remove( const elemType &e )
{
   _root->find_node( _root, e );
}

#ifndef     NODE_H

#define     NODE_H

#include    <string>

using namespace std;

template< typename T >
class Node
{
   public:
       Node( const T &);

       T  value( )  const;
       T  value( const T & );

       void insert_value( const T & );
       void inorder( const Node * );
 void find_node( Node< T > *, const T & );
 void delete_node( Node< T > *, Node< T > * );

       Node *  left ( ) const;
       Node *  left ( Node * );
       Node *  right( ) const;
       Node *  right( Node * );

   private:
       T       _value;
       Node *  _left;
       Node *  _right;

       Node::Node( const Node & );
       Node &operator =( const Node & );
};


template< typename T >
inline Node< T >::Node( const T &rhs )
{
   _value = rhs;                       // assign rhs to _value
   _left  =  _right = 0;               // node is not part of a tree yet
}


template< typename T >
inline T Node< T >::value( ) const
{
   return _value;
}


template< typename T >
inline T Node< T >::value( const T &rhs )
{
   _value = rhs;                       // new value for _value
   return _value;
}


template< typename T >
inline Node< T > *Node< T >::left( ) const
{
   return _left;
}


template< typename T >
inline Node< T > *Node< T >::left( Node< T > *rhs )
{
   _left = rhs;
   return _left;
}


template< typename T >
inline Node< T > *Node< T >::right( ) const
{
   return _right;
}


template< typename T >
inline Node< T > *Node< T >::right( Node< T > *rhs )
{
   _right = rhs;
   return _right;
}


template< typename T >
inline void Node< T >::insert_value( const T &val )
{
   if( val == _value )
   {
       return;                     // value already in the tree
   }
   if( val < _value )              // val should appear at the left
   {
       if( ! _left )               // no left subtree ?
       {                           // add new node here
           _left = new Node( val );
       }
       else                        // try the subtree
       {
           _left->insert_value( val );
       }
   }
   else                            // val should appear at the right
   {
       if( ! _right )              // no right subtree ?
       {                           // add new node here
           _right = new Node( val );
       }
       else                        // try the subtree
       {
           _right->insert_value( val );
       }
   }
}


template< typename T >
inline void Node< T >::inorder( const Node< T > *pt )
{
   if( pt )
   {
       inorder( pt->_left );
       cout << std::hex << pt->_left << std::dec << '\t';
       cout << std::hex << pt << std::dec << '\t';
       cout << std::hex << pt->_right << std::dec << '\t';
       cout << pt->_value << '\n';
       inorder( pt->_right );
   }
}

template< typename T >
inline void Node< T >::find_node( Node< T > *p, const T &val )
{
Node< T > *parent = 0;
while( p ) {
 if( val < p->value( ) ) {
  parent = p;
  p = p->left( );
 } else if( val > p->value( ) ) {
  parent = p;
  p = p->right( );
 } else {
  delete_node( p, parent );
  break;
 }
}
}

template< typename T >
inline void Node< T >::delete_node( Node< T > *p, Node< T > *parent )
{
if( parent ) {
 if( parent->left( ) == p ) {
  if( !p->left( ) && !p->right( ) ) {
   parent->left( 0 );
   delete p;
  } else if( p->left( ) && !p->right( ) ) {
   parent->left( p->left( ) );
   delete p;
  } else if( !p->left( ) && p->right( ) ) {
   parent->left( p->right( ) );
   delete p;
  } else {
   Node< T > *temp = p->right( );
   while( temp->right( ) ) {
    temp = temp->right( );
   }
   temp->right( parent );
   parent->left( 0 );
   delete p;
  }
 } else if( parent->right( ) == p ) {
  if( !p->left( ) && !p->right( ) ) {
   parent->right( 0 );
   delete p;
  } else if( p->left( ) && !p->right( ) ) {
   parent->right( p->left( ) );
   delete p;
  } else if( !p->left( ) && p->right( ) ) {
   parent->right( p->right( ) );
   delete p;
  } else {
   Node< T > *temp = p->left( );
   while( temp->left( ) ) {
    temp = temp->left( );
   }
   temp->left( parent );
   parent->right( 0 );
   delete p;
  }
 }
} else {
 Node< T > *temp = p->right( );
 while( temp->left( ) ) {
  temp = temp->left( );
 }
 temp->left( p->left( ) );
 //point _root to p->right( )
 delete p;
}
}

#endif

template< typename T >
inline void Node< T >::find_node( Node< T > *&root, const T &val)
{
if( val < _value ) {
 if( _left ) {
  _left->find_node( _left, val );  //go left if val < node
 }
} else if( val > _value ) {
 if( _right ) {
  _right->find_node( _right, val ); //go right if val > node
 }
} else {
 delete_node( root );     //if not > or < must be ==
}
}

template< typename T >
inline void Node< T >::delete_node( Node< T > *&p )
{
Node< T > *temp;      //safe pointer to use instead of *&
if( !p->_left ) {                       //if p has no left (or is leaf)
 temp = p;
 p = p->_right;
 delete temp;
} else if( !p->_right ) {               //if p has no right
 temp = p;
 p = p->_left;
 delete temp;
} else {                                //if p has two children
 temp = p->_right;
 while( temp->_left ) {              //find p's successor (the left...
  temp = temp->_left;    //... most node to the right of p)
 }
 temp->_left = p->_left;    //point p's successor to p's left
 temp = p;
 p = p->_right;
 delete temp;      //delete what p pointed to
}
}