#include <iostream>
using namespace std;

struct tree
{
    int inf;
    tree* left;
    tree* right;
};

tree* addtree(tree* root, int inf)
{
    if (root == NULL)
    {
        root = new tree;
        root->inf = inf;
        root->left = NULL;
        root->right = NULL;
    }
    else  if (inf < root->inf)
        root->left = addtree(root->left,inf);
    else
        root->right = addtree(root->right,inf);
    return root;
}

tree* addtree_b(int left, int right, int arr[])   //функция создания нового дерева
{
    tree* root;
    int i;
    if (left > right)return NULL;

    i = (left + right) / 2;
    root = new tree;
    root->inf = arr[i];
    root->left = addtree_b(left, i - 1, arr);
    root->right = addtree_b(i + 1, right, arr);
    return root;
}


void pre_showtree(tree* root)
{
    if (root)
    {
        cout << root->inf << endl;
        pre_showtree(root->left);
        pre_showtree(root->right);
    }
}

void insertsort(int arr[], int size)
{
    int i, j;
    int temp;
    for (i = 1; i < size; ++i)
    {
        temp = arr[i];
        for (j = i - 1; j >= 0 && temp < arr[j]; j--)
        {
            arr[j + 1] = arr[j];

        }
        arr[j + 1] = temp;
    }
}

void searchmax(tree* root)
{
    if (root->left == NULL)
    {
        cout << root->inf;
        return;
    }
    root = root->left;


    while (root)
    {
        if (root->left == NULL && root->right == NULL)
        {

            delete root;
            root = NULL;
            return ;
        }
        root = root->right;
    }


}




int main()
{
    tree* root = NULL;
    tree* rmax = NULL;
    bool ques=false;
    char q;
    int size;
    cout << "enter the size: ";
    cin >> size;
    int* arr = new int[size];
    for (int i = 0; i < size; ++i)
    {
        cout << "\n enter arr[" << i << "]: ";
        cin >> arr[i];
    }
    cout << endl << " balanced tree (y/n)";

    cin >> q;
    while (!ques)
    {
        if (q == 'y')
        {
            insertsort(arr, size);
            for (int i = 0; i < size; ++i)
            {
                cout << arr[i] << " ";

            }
            root = addtree_b(0, size - 1, arr);
            ques = true;
        }
        else if (q == 'n')
        {
            int inf;
            for (int i = 0; i < size; ++i)
            {
                inf = arr[i];
                root=addtree(root,inf);
                cout << arr[i] << " ";

            }
            ques = true;

        }
        else
        {
            cout << "enter  y or n";
            cin >> q;
        }
    }
    cout << endl;
    cout << "its ur tree(pre-order): ";
    pre_showtree(root);
    cout << endl;
    cout << "answer :";
    searchmax(root);
    cout << "its ur tree(pre-order): ";
    pre_showtree(root);


    return 0;
    }