#include <iostream>
#include<conio.h>
using namespace std;
struct leaf {
    int index;
    leaf* left;
    leaf* right;
};

void tree(leaf** first) {
    if ((*first) == nullptr) {
        cout << "Корінь дерева пустий." << endl;
        int num;
        cout << "Введіть індекс кореня дерева: ";
        cin >> num;
        (*first) = new leaf;
        (*first)->left = nullptr;
        (*first)->right = nullptr;
        (*first)->index = num;
    }
    else {
        return;
    }
    leaf* last = nullptr;
    last = (*first);
    leaf* Num = new leaf;
    for (int i = 0; i < 10; i++) {
        cout << "Введіть значення листя дерева: ";
        cin >> Num->index;
        while (last->left != nullptr && last->right != nullptr) {
            if (last->index > Num->index && last->left == nullptr) {
                last = last;
                break;
            }
            else {
                last = last->left;
            }
            if (last->index < Num->index && last->right == nullptr) {
                last = last;
                break;
            }
            else {
                last = last->right;
            }
        }
        if (last->index > Num->index) {
            last->left = new leaf;
            last = last->left;
            last->index = Num->index;
            last->left = nullptr;
            last->right = nullptr;
        }
        else {
            if (last->index < Num->index) {
                last->right = new leaf;
                last = last->right;
                last->index = Num->index;
                last->left = nullptr;
                last->right = nullptr;
            }
        }

        last = (*first);

    }
}
void printtree(leaf** root, int level) {
    if ((*root)!=nullptr) {
        printtree(&(*root)->right,level+1);
        for (int i = 0; i <= level; i++) {
            cout << " ";
        }
        cout << (*root)->index << endl;
        printtree(&(*root)->left, level + 1);


    }
}



int main(void) {
    setlocale(LC_ALL, "Ukr");
    leaf* first = nullptr;
    tree(&first);
    printtree(&first, 2);




    _getch();
    return 0;
}