// C로 이진트리를 직접 만들어서 문제를 푸는 과정입니다. 
#include <stdio.h>
#include <stdlib.h>
// bool 타입을 새로 만들었습니다.
#define false 0
#define true 1

typedef int bool;

// 이진트리를 구성할 스트럭을 만듭니다.
typedef struct binary_tree
{
    int value;
    
    struct binary_tree* left;
    struct binary_tree* right;
}Tree;

// root 포인터를 널로 설정합니다. 
Tree* root = NULL;

// 이진트리 포인터에 새로운 값을 할당하고 리턴해주는 함수입니다. 
Tree* tree_alloc(Tree* p, int x)
{
    p = malloc(sizeof(Tree));
    p -> value = x;
    p -> left = NULL;
    p -> right = NULL;
    return p;
}
// 이진트리에 입력을 하는 함수입니다. 
// 기존에 입력을 그대로 받아 이진트리를 구성합니다. 
void insert(int x)
{
// 만약에 루트가 NULL 즉 아직 입력을 못 받은 상태라면 처음 한번만 할당해줍니다. 
    if(root == NULL)
    {
        root = malloc(sizeof(Tree));
        root -> value = x;
        root -> left = NULL;
        root -> right = NULL;
        return ;
    }
    
	// 부모노드(parent)와 자식노드(p)를 처음에는 root로 설정해줍니다. 
    Tree* p = root;
    Tree* parent = root;
	
	// while 루프에서 마지막에 할당된 쪽이 오른쪽인지 왼쪽인지 판별하는 불린 값입니다. 
    bool right = false;
    bool left = false;
	
	
    while(p)
    {
	// while루프를 돌때마다 초기화 해줍니다. 마지막 while루프에 들어가지 못할 때가 진짜 필요한 값이기 때문입니다. 
        right = false;
        left = false;
        parent = p;
		
        // x 값이 p 값보다 크면 p를 오른쪽 자식으로 이동시킵니다.
        if(x > p -> value)
        {
            p = p -> right;
            right = true;
        }
		 
		 // x 값이 p 값보다 작으면 p를 왼쪽 자식으로 이동시킵니다.
        else if(x < p -> value)
        {
            p = p -> left;
            left = true;
        }
    }
    
	// 자식에 새롭게 메모리를 할당하고 값을 넣어줍니다.
    p = tree_alloc(p, x);
	// 부모와 새롭게 만든 자식을 연결해줍니다.
    if(right == true)
    {
        parent -> right = p;
    }
    else if(left == true)
    {
        parent -> left = p;
    }
}

// 재귀적으로 후위 출력하는 함수입니다.
void print(Tree* start)
{
    Tree* left = start -> left;
    Tree* right = start -> right;
	
	// left가 있으면 right를 출력하기전 재귀적으로 다시 print를 불러 right값들은 스택으로 쌓아둡니다. 
    if(left != NULL)
    {
        another_print(left);
        printf("%d\n", left -> value);
    }
    // right값을 출력할 때에도 printf를 아래로 작성함으로써 자식노드 끝까지 내려간 후에 출력하도록 합니다. 
    if(right != NULL)
    {
        another_print(right);
        printf("%d\n", right -> value);
    }
    if(start == root)
    {
        printf("%d\n", start -> value);
    }
}

int main()
{
    int n;
	// EOF를 입력받으면 종료됩니다. 
    while(scanf("%d", &n) != EOF)
    {
        insert(n);
    }
    print(root);
}