//  (C) Porkolab 2003
//
//  A.5.5.
//   
//  Catching exception thrown in the constructor
//  in the new expression, and call correct delete

#include <iostream>
#include <new>
#include <memory>

using namespace std;

struct node
{
          node( int v);
    void  print() const;

    static void *operator new( size_t sz, int i) throw (bad_alloc);
    static void  operator delete(void *p) throw();
    //static void  operator delete(void *p, int) throw();

    int   val;
    node *left;
    node *right;
};

// members
node::node( int v)        // the constructor
{
    left = right = 0;
    val = v;
    if ( val == -1 )
        throw -1;
}
void node::print() const    // a const member function
{
    cout << val << " ";
}

// global new and delete
void *operator new( size_t sz, int i) throw (bad_alloc)
{
    // not for MSVC++ !
    std::cerr << "::new(int): " << i << std::endl;
    return malloc(sz);
}
void operator delete( void *p, int i) throw ()
{
    // not for MSVC++ !
    std::cerr << "::delete(int): " << i << std::endl;
    free(p);
}
void operator delete( void *p) throw ()
{
    // not for MSVC++ !
    std::cerr << "::delete(): " << std::endl;
    free(p);
}

// member new and delete
void *node::operator new( size_t sz, int i) throw (bad_alloc)
{
    std::cerr << "node::new(int): " << i << std::endl;
    return ::operator new(sz,i);
}
void node::operator delete(void *p) throw()
{
    node *np = reinterpret_cast<node *>(p);
    std::cerr << "node::delete(): " << np->val << std::endl;
    ::operator delete(p,np->val);
}
/*void node::operator delete(void *p, int i) throw()
{ 
    node *np = reinterpret_cast<node *>(p);
    std::cerr << "node::delete(int): " << np->val << std::endl;
    ::operator delete(p,np->val);
}
*/

void insert( node *&r, int v);  // insert into (sub)tree
void print( node *r);           // print (sub)tree
void destroy( node *&r );       // destroy (sub)tree

int main()
{
    node *root = 0;
    int   i;

    while ( cin >> i )
    try {
        insert( root, i);
    }
    catch( ... ) { }
    print( root);
    destroy( root);

    return 0;
}
void print( node *r)
{
    if ( r )
    {
        print( r->left);
        r->print();
        print( r->right);
    }
}
void insert( node *&r, int v)
{
    if ( r )
    {
        insert( v < r->val ? r->left : r->right, v);
    }
    else
    {
        r = new(v) node(v);
    }
}
void destroy( node *&r)
{
    if ( r )
    {
        destroy( r->left);
        destroy( r->right);
        delete r;
        //r->~node();
        //node::operator delete(r,99);
        r = 0;
    }
}