#include <iostream>
using namespace std;

class No
{
private:
    No *esq, *dir;
    int chave;

public:
    No(int chave)
    {
        this->chave = chave;
        esq = NULL;
        dir = NULL;
    }

    int getChave()
    {
        return chave;
    }

    // funções getters e setters

    No* getEsq()
    {
        return esq;
    }

    No* getDir()
    {
        return dir;
    }

    void setEsq(No *no)
    {
        esq = no;
    }

    void setDir(No *no)
    {
        dir = no;
    }
};

class Arvore
{
private:
    No *raiz;

public:
    Arvore()
    {
        raiz = NULL;
    }

    void inserir(int chave)
    {
        if(raiz == NULL) // verifica se a árvore está vazia
            raiz = new No(chave); // cria um novo nó
        else
            inserirAux(raiz, chave);
    }

    void inserirAux(No *no, int chave)
    {
        // se for menor, então insere à esquerda
        if(chave < no->getChave())
        {
            // verifica se a esquerda é nulo
            if(no->getEsq() == NULL)
            {
                No *novo_no = new No(chave);
                no->setEsq(novo_no); // seta o novo_no à esquerda
            }
            else
            {
                // senão, continua percorrendo recursivamente
                inserirAux(no->getEsq(), chave);
            }
        }
        // se for maior, então insere à direita
        else if(chave > no->getChave())
        {
            // verifica se a direita é nulo
            if(no->getDir() == NULL)
            {
                No *novo_no = new No(chave);
                no->setDir(novo_no); // seta o novo_no à direita
            }
            else
            {
                // senão, continua percorrendo recursivamente
                inserirAux(no->getDir(), chave);
            }
        }
        // se for igual, não vai inserir
        // não pode existir 2 chaves iguais
    }

    No* getRaiz()
    {
        return raiz;
    }

    void emOrdem(No* no)
    {
        if(no != NULL)
        {
            emOrdem(no->getEsq());
            cout << no->getChave() << " ";
            emOrdem(no->getDir());
        }
    }
};

int main(int argc, char *argv[])
{
    Arvore arv;
    int vl=0;


    // insere as chaves
    while(1){
    cin>>vl;
    arv.inserir(vl);
    cout << "Percorrendo em ordem...\n";
    arv.emOrdem(arv.getRaiz());
    }

    // percorre em ordem iniciando da raiz
    cout << "Percorrendo em ordem...\n";
    arv.emOrdem(arv.getRaiz());

    return 0;
}