WA56

#include <iostream>

struct Node
{
    int key;
    int idx;
    Node* left;
    Node* right;
    Node* parent;
};

void find_parent(
    int idx_left, int idx_right, int idx, Node* tree, int max_l, int max_r, int* l, int* r)
{

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

    is_greater ? curr = &tree[idx_right] : curr = &tree[idx_left];

    if (curr->key <= tree[idx].key && curr->right == NULL)
    {
        tree[idx].parent = curr;
        curr->right = &tree[idx];

        if (is_greater & tree[idx].key > max_r)
            *r = idx;

        if (!is_greater & tree[idx].key > max_l)
            *l = idx;
    }

    else if (curr->key > tree[idx].key)
    {
        is_greater ? idx_right = tree[idx_right].left->idx : idx_left = tree[idx_left].left->idx;
        find_parent(idx_left, idx_right, idx, tree, max_l, max_r, l, r);
    }

    else if (curr->right != NULL)
    {
        is_greater ? idx_right = tree[idx_right].right->idx : idx_left = tree[idx_left].right->idx;
        find_parent(idx_left, idx_right, idx, tree, max_l, max_r, l, r);
    }

    return;
}


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

    int max_l, max_r;

    (*idx_left == 0) ? max_l = -1 : max_l = tree[*idx_left].key;
    (*idx_right == 0) ? max_r = -1 : max_r = tree[*idx_right].key;


    while (k < n - 1 & tree[k + 1].key < tree[k].key)
    {
        tree[k].left = &tree[k + 1];
        tree[k + 1].parent = &tree[k];
        k++;
    }

    if (k + 1 < n)
    {
        find_parent(*idx_left, *idx_right, k + 1, tree, max_l, max_r, idx_left, idx_right);
    }

    if (k + 2 < n)
    {
        f(idx_left, idx_right, k + 1, tree, n);
    }
}

void preorderTraversal(Node* x)
{
    if (x != NULL)
    {
        std::cout << x->key << " ";
        preorderTraversal(x->left);
        preorderTraversal(x->right);
    }
    return;
}

void inorderTraversal(Node* x)
{
    if (x != NULL)
    {
        inorderTraversal(x->left);
        std::cout << x->key << " ";
        inorderTraversal(x->right);
    }
    return;
}

void postorderTraversal(Node* x)
{
    if (x != NULL)
    {
        postorderTraversal(x->left);
        postorderTraversal(x->right);
        std::cout << x->key << " ";
    }
    return;
}

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

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

    int idx_left = 0, idx_right = 0;
    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;
        std::cin >> tree[i].key;
    }


    f(&idx_left, &idx_right, 0, tree, n);

    postorderTraversal(&tree[0]);
    std::cout << std::endl;
    inorderTraversal(&tree[0]);

    return 0;
}