#include <iostream>
#include <string>
#include <map>
#include <stdlib.h>
#include <vector>

//////////////////////////////////////////////////////////////////////////////

using namespace std;

//////////////////////////////////////////////////////////////////////////////

class Tree
{
private:
    struct Leaf
    {
        int data;
        Leaf* l;
        Leaf* r;
    };
public:
    // ctor & dtor
    Tree() { p = NULL; }
    Tree(const Tree& rhs) { p = copy(rhs.p); }
    ~Tree() { destroy(p); }

    // add & remove
    bool add(int n);
    bool del(int n);

    // traversal
    void transverse();
    void in(Leaf *q);
    void pre(Leaf *q);
    void post(Leaf *q);
protected:
    static Leaf* copy(const Leaf* rhs);
    static void destroy(Leaf* q);
    void find(int n, Leaf*& parent, Leaf*& x);
private:
    Leaf* p;
};

//////////////////////////////////////////////////////////////////////////////

string
readIntStr(istream& is)
{
    string res;
    char c;
    for (c = is.get(); !isdigit(c) && (c != '\n') && !is.eof(); c = is.get());
    if (c == '\n') return res;
    while (isdigit(c))
    {
        res.push_back(c);
        c = is.get();
    }
    return res;
}

//////////////////////////////////////////////////////////////////////////////

bool
Tree::add(int n)
{
    Leaf* t;
    Leaf* parent;
    Leaf* found;
    find(n, parent, found);

    // already exists?
    if (found != NULL) return false;

    t = new Leaf();
    t->data=n;
    t->l=NULL;
    t->r=NULL;

    // empty tree -> new root
    if (parent==NULL)
    {
        p = t;
        return true;
    }

    // link to new Leaf from parent
    if (n < parent->data)
    {
        parent->l = t;
    }
    else
    {
        parent->r = t;
    }

    return true;
}

//////////////////////////////////////////////////////////////////////////////

bool
Tree::del(int num)
{
    Leaf* parent = NULL;
    Leaf* x = NULL;
    Leaf* xsucc;

    // no such key?
    find(num, parent, x);
    if (x == NULL) return false;

    // x has 2 children -> translate to removal of x's inorder successor
    if ((x->l != NULL) && (x->r != NULL))
    {
        parent = x;
        xsucc = x->r;
        while (xsucc->l != NULL)
        {
            parent = xsucc;
            xsucc = xsucc->l;
        }
        x->data = xsucc->data;
        x=xsucc;
    }

    // x has no child?
    if ((x->l == NULL) && (x->r == NULL))
    {
        if (parent == NULL)
            p = NULL;
        if (parent->r == x)
            parent->r = NULL;
        else
            parent->l = NULL;
        delete x;
        return true;
    }

    // x has only right child?
    if ((x->l == NULL) && (x->r != NULL))
    {
        if (parent == NULL)
            p = x->r;
        else if (parent->l == x)
            parent->l = x->r;
        else
            parent->r = x->r;
        delete x;
        return true;
    }

    // x has only left child
    if (parent == NULL)
        p = x->l;
    if (parent->l == x)
        parent->l = x->l;
    else
        parent->r = x->l;
    delete x;
    return true;
}

//////////////////////////////////////////////////////////////////////////////

void
Tree::transverse()
{
    cout << "\n1.InOrder\n2.Preorder\n3.Postorder\nChoice: ";
    string str = readIntStr(cin);
    if (str.empty()) return;
    int c = atoi(str.c_str());
    switch (c)
    {
        case 1:
            in(p);
            break;
        case 2:
            pre(p);
            break;
        case 3:
            post(p);
            break;
    }
}

//////////////////////////////////////////////////////////////////////////////

void
Tree::in(Leaf *q)
{
    if (q == NULL) return;
    in(q->l);
    cout << "\t" << q->data << endl;
    in(q->r);
}

//////////////////////////////////////////////////////////////////////////////

void
Tree::pre(Leaf *q)
{
    if (q == NULL) return;
    cout << "\t" << q->data << endl;
    pre(q->l);
    pre(q->r);
}

//////////////////////////////////////////////////////////////////////////////

void
Tree::post(Leaf *q)
{
    if (q == NULL) return;
    post(q->l);
    post(q->r);
    cout << "\t" << q->data << endl;
}

//////////////////////////////////////////////////////////////////////////////

Tree::Leaf*
Tree::copy(const Tree::Leaf* rhs)
{
    if (rhs == NULL) return NULL;
    Leaf* lhs = new Leaf();
    lhs->data = rhs->data;
    lhs->l = copy(rhs->l);
    lhs->r = copy(rhs->r);
    return lhs;
}

//////////////////////////////////////////////////////////////////////////////

void
Tree::destroy(Leaf *q)
{
    if (q == NULL) return;
    destroy(q->l);
    destroy(q->r);
    delete q;
}

//////////////////////////////////////////////////////////////////////////////

void
Tree::find(int n, Leaf*& parent, Leaf*& x)
{
    parent = x = NULL;
    if (p == NULL) return;

    Leaf *q = p;
    while (q != NULL)
    {
        if (q->data == n)
        {
            x = q;
            return;
        }
        if (n < q->data)
        {
            parent = q;
            q = q->l;
        }
        else
        {
            parent = q;
            q = q->r;
        }
    }
}

//////////////////////////////////////////////////////////////////////////////

int
main()
{
    // stack vars
    Tree t;
    map<int,int> count;
    map<int,int>::iterator it;
    string str;
    size_t i, num;

    // populate count[]
    for (;;)
    {
        str = readIntStr(cin);
        if (str.empty()) break;
        num = atoi(str.c_str());
        ++count[num];
    }

    // let data[] = keys in count[]
    num = count.size();
    vector<int> data(count.size(), 0);
    for (it = count.begin(), i = 0; it != count.end(); ++it, ++i)
    {
        data[i] = (*it).first;
    }

    // add the keys to the tree
    for (i = 0; i < num; ++i)
    {
        t.add(data[i]);
    }

    // remove the first key
    if (num > 0)
    {
        cout << "removing the first key!" << endl;
        t.del(data[0]);
    }

    // perform transverse
    t.transverse();

    // done
    return 0;
}