#include<iostream>
using namespace std;

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};


void Postorder(Node* root) {
    if (root == NULL) return;

    Postorder(root->left);
    Postorder(root->right);
    cout << root->data << " ";
}

Node* Insert(Node* root, int data) {
    if (root == NULL) {
        root = new Node();
        root->data = data;
        root->left = root->right = NULL;
    }
    else if (data <= root->data)
        root->left = Insert(root->left, data);
    else
        root->right = Insert(root->right, data);
    return root;
}

int main() {
    setlocale(0, "");
    Node* root = NULL;
    int size = 0;
    cout << "Array size: ";
    cin >> size;
    int* arr = new int[size];

    for (int i = 0; i < size; i++) {
        arr[i] = rand() % 10;
    }
    for (int i = 0; i < size; i++) {
        root = Insert(root, arr[i]);
    }
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
    cout << "Eлементи дерева в префiксному порядку: " << endl;
    Postorder(root);
    system("Pause");
}