// sorting integers by binary tree 
// using reference
// and constructor

#include <iostream>^M
#include <new>

using namespace std;

struct node
{
         node( int v);
    void print() const;
^M
    void *operator new( size_t sz) ^M
    { ^M
        std::cerr << "node::new" << std::endl; ^M
        return ::operator new(sz);^M
    }^M
    void  operator delete(void *p)^M
    { ^M
        std::cerr << "node::delete" << std::endl;^M
        ::operator delete(p);^M
    }
^M
    int   val;
    node *left;
    node *right;
};
node::node( int v)        // the constructor
{
    left = right = 0;
    val = v;
}
void node::print() const    // a const member function
{
    cout << val << " "; 
}

void *operator new( size_t sz)^M
{^M
    //  std::cerr << "::new" << std::endl;^M
    return malloc(sz);^M
}^M
void operator delete( void *p)^M
{^M
    std::cerr << "::delete" << std::endl;^M
    // return free(p);^M
    free(p);^M
}^M
^M
void insert( node *&r, int v);  // insert into (sub)tree
void print( node *r);           // print (sub)tree

int main()
{
    node *root = 0;
    int   i;
    
    while ( cin >> i )
    {
        insert( root, i);
    }
    print( 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 node(v);
    }
}