#include <stdio.h>;

struct btree {
    int value;
    struct btree *left, *right;
};

// Включение вершины в дерево
void Ins_Btree(int val, btree **q) {
    if (*q == NULL) {//Нашли место для добавления
        *q = new btree;
        (*q)->left = NULL;
        (*q)->right = NULL;
        (*q)->value = val;
        return;
    }
    if ((*q)->value > val)
// Добавляем в левое поддерево
        Ins_Btree(val, &(*q)->left);
    else
// Добавляем в правое поддерево
        Ins_Btree(val, &(*q)->right);
}

//Вывод содержимого дерева
void Print_Btree(btree *p) {
    if (p == NULL) return;
    Print_Btree(p->left);
    printf("%d ", p->value);
    Print_Btree(p->right);
}

btree *get_min(btree *tree) {
    if (tree->left == NULL) return tree;
    get_min(tree->left);
}

btree *get_max(btree *tree) {
    if (tree->right == NULL) return tree;
    get_max(tree->right);
}

void swap_min_max(btree *tree) {
    int temp = get_min(tree)->value;
    get_min(tree)->value = get_max(tree)->value;
    get_max(tree)->value = temp;
}

int main() {
    int d;
    btree *root = NULL;
    puts("Дерево. Ввод чисел:");
    while (1) {
        scanf("%d", &d);
        if (d == 0)break;
        Ins_Btree(d, &root);
    }
    Print_Btree(root);
    puts("\n");
    swap_min_max(root);
    Print_Btree(root);
}