много принтов работает

#include <iostream>
using namespace std;

struct Node
{
    int key; // ключ узла
    int idx;
    Node* left; // указатель на левого потомка
    Node* right; // указатель на правого потомка
    Node* parent; // указатель на предка
};

/*
Первая вершина всегда будет в корне. Затем, пока не будут использованы все значения,
будем последовательно подвешивать левых сыновей к последней добавленной вершине, пока не найдём
номер,
нарушающий убывающую последовательность,

а для каждого такого номера будем искать вершину без правого потомка,
хранящую наибольшее значение, не превосходящее того, которое хотим поставить, и подвешиваем к ней
элемент
с таким номером в качестве правого сына.

Когда мы, желая найти такую вершину, встречаем какую-нибудь другую,
уже имеющую правого сына, проходим по ветке вправо. Мы имеем на это право, так как если такая
вершина стоит,
то процедура обхода в ней уже побывала и поворачивала вправо, поэтому спускаться в другую сторону
смысла не имеет.

Вершину с максимальным ключом, с которой будем начинать поиск, будем запоминать. Она будет
обновляться каждый раз,
когда появится новый максимум.
*/

void find_parent(int* l, int* r, int idx, Node* tree)
{
    cout << "Зашёл в поиск родителя для ключа " << tree[idx].key << endl;

    //сравниваю на больше меньше и решаю куда идти пока не встречу без правого
    //Сравниваю с корнем и понимаю в максимум какой ветки смотреть

    int idx_left = *l;
    int idx_right = *r;

    bool is_greater;
    is_greater = tree[0].key < tree[idx].key;

    /* Думаю можно так (вне этой фун вообще)
    if (is_greater)
        idx_right = idx;
    else
        idx_left = idx;
    */

    Node* curr;
    if (is_greater)
    {
        curr = &tree[idx_right];
        cout << "Т.к. ключ больше верны то смотрим правый макс, curr =  " << curr->key << endl;
    }
    else
    {
        curr = &tree[idx_left];
        cout << "Т.к. ключ меньше вершины то смотрим левый макс, curr = " << curr->key << endl;
    }

    if (curr->key <= tree[idx].key && curr->right == NULL)
    {
        cout << "Нашёл родителя - " << curr->key << endl;

        tree[idx].parent = curr;
        curr->right = &tree[idx];
        cout << "есть ли указатель " <<(curr->right->key) << endl;

        if (is_greater)
        {
            idx_right = tree[idx].idx;
            *r = idx;
            cout << "теперь idx_right = " << idx_right << endl;
        }
        else
        {
            idx_left = tree[idx].idx;
            *l = idx;
            cout << "теперь *l = " << *l << endl;
        }
    }

    else if (curr->key > tree[idx].key)
    {
        cout << "макс больше ключа, запускаю от левого сына" << endl;
        if (is_greater)
        {
            *r = tree[idx_right].left->idx;
            find_parent(l, r, idx, tree);
        }
        else
        {
            *l = tree[idx_left].left->idx;
            find_parent(l, r, idx, tree);
        }
    }

    else if (curr->right != NULL)
    {
        cout << "справа занято, запускаю от правого сына" << endl;
        if (is_greater)
        {
            // int* new_idx_right = tree[idx_right].right->idx;
            *r = tree[idx_right].right->idx;
            find_parent(l, r, idx, tree);
        }
        else
        {
            // int* new_idx_left = tree[idx_left].left->idx;
            *l = tree[idx_left].right->idx;
            find_parent(l, r, idx, tree);
        }
    }


    cout << "Конец" << endl;
    return;
}


void f(int k, Node* tree, int n, int* idx_left, int* idx_right)
{

    while (k < n - 1 && tree[k + 1].key <= tree[k].key) //<= ?
    {
        cout << "k= " << k << " tree[k + 1].key ,tree[k].key = " << tree[k + 1].key << " " << tree[k].key << endl;
        cout << "in" <<  endl;
        tree[k].left = &tree[k + 1];
        tree[k + 1].parent = &tree[k];
        k++;
    }

    if (k + 1 <= n - 1)
    {
        cout << tree[k + 1].key << " нарушила убывание, ищу куда вставить ее" << endl;
        find_parent(idx_left, idx_right, k + 1, tree); //Обновляем вершину с макс ключом и вставляем k+1-ую
        cout << "есть ли указатель " <<(tree[1].right == NULL) << endl;
    }
    if (k + 2 <= n - 1)
    { //Если посмотрели еще не все вершины то запускаем
        cout << "Ещё не все посмотрели, запускаю от " << tree[k + 1].key << endl;
        f(k + 1, tree, n, idx_left, idx_right);
    }
}

void preorderTraversal(Node* x)
{
    if (x != NULL)
    {
        cout << "Зашёл, текущий ключ = ";
        cout << x->key << endl;
        preorderTraversal(x->left);
        preorderTraversal(x->right);
    }
    return;
}

int main()
{
    int n;
    cin >> n;

    Node tree[n];
    for (int i = 0; i < n; ++i)
    {
        tree[i].right = NULL;
        tree[i].left = NULL;
        tree[i].parent = NULL;
        tree[i].idx = i;
        cin >> tree[i].key; //Массив вершин, в i-ой вершине i-ый ключ
    }

    Node* curr = &tree[0]; // curr указывает на верш с макс ключом  с которой будем начинать поиск
    int idx_left = 0, idx_right = 0;
    f(0, tree, n, &idx_left, &idx_right);

    for (int i = 0; i < n; ++i)
    {
        cout << "i= " << tree[i].key << ": ";
        if (tree[i].left != NULL)
            cout << tree[i].left->key << " ";
        if (tree[i].right != NULL)
            cout << tree[i].right->key << " ;";
        cout << endl;

    }
    cout << endl;

    cout << "preoder " << endl;
    preorderTraversal(&tree[0]);
    return 0;
}