---

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <vector>
using namespace std;

struct Node {
    int key;
    Node* left;
    Node* right;
    int height;
    Node(int k) : key(k), left(nullptr), right(nullptr), height(1) {}
};

int height(Node* n) { return n ? n->height : 0; }
int bfactor(Node* n) { return n ? height(n->left) - height(n->right) : 0; }
void fixHeight(Node* n) {
    if (n) n->height = 1 + max(height(n->left), height(n->right));
}

Node* rotateRight(Node* p) {
    Node* q = p->left;
    p->left = q->right;
    q->right = p;
    fixHeight(p);
    fixHeight(q);
    return q;
}

Node* rotateLeft(Node* p) {
    Node* q = p->right;
    p->right = q->left;
    q->left = p;
    fixHeight(p);
    fixHeight(q);
    return q;
}

Node* balance(Node* p) {
    fixHeight(p);
    if (bfactor(p) == 2) {
        if (bfactor(p->left) < 0) p->left = rotateLeft(p->left);
        return rotateRight(p);
    }
    if (bfactor(p) == -2) {
        if (bfactor(p->right) > 0) p->right = rotateRight(p->right);
        return rotateLeft(p);
    }
    return p;
}

Node* insert(Node* p, int key) {
    if (!p) return new Node(key);
    if (key < p->key) p->left = insert(p->left, key);
    else if (key > p->key) p->right = insert(p->right, key);
    else return p;
    return balance(p);
}

void deleteTree(Node* p) {
    if (!p) return;
    deleteTree(p->left);
    deleteTree(p->right);
    delete p;
}

void inorder(Node* p) {
    if (!p) return;
    inorder(p->left);
    cout << p->key << " ";
    inorder(p->right);
}

// Задание 8: подсчёт количества листьев на каждом уровне
void countLeavesPerLevel(Node* p, int level, vector<int>& leafCount) {
    if (!p) return;
    
    // Увеличиваем вектор, если уровень ещё не встречался
    if (level >= leafCount.size()) {
        leafCount.push_back(0);
    }
    
    // Если узел - лист (нет детей), увеличиваем счётчик на этом уровне
    if (p->left == nullptr && p->right == nullptr) {
        leafCount[level]++;
    }
    
    countLeavesPerLevel(p->left, level + 1, leafCount);
    countLeavesPerLevel(p->right, level + 1, leafCount);
}

int main() {
    srand(time(0));
    Node* root = nullptr;

    cout << "Создание дерева из 10 случайных чисел [-50, 50]:" << endl;
    for (int i = 0; i < 10; i++) {
        int val = rand() % 101 - 50;
        root = insert(root, val);
    }

    cout << "Дерево (возрастание): ";
    inorder(root);
    cout << endl;

    vector<int> leafCount;
    countLeavesPerLevel(root, 0, leafCount);

    cout << "\nКоличество листьев на каждом уровне:" << endl;
    if (leafCount.empty()) {
        cout << "Дерево пусто" << endl;
    } else {
        for (size_t i = 0; i < leafCount.size(); i++) {
            cout << "Уровень " << i << ": " << leafCount[i] << " листьев" << endl;
        }
    }

    deleteTree(root);
    return 0;
}