#include <iostream>
using namespace std;

struct Node {
    int key;
    Node* left;
    Node* right;
} *root = NULL; // Външен указател

// Функция за създаване на нов възел
Node* createNode(int key) {
    Node* newNode = new Node();
    newNode->key = key;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Функция за добавяне на нов възел в дървото
Node* insertNode(Node* root, int key) {
    if (root == NULL) {
        return createNode(key);
    }

    if (key < root->key) {
        root->left = insertNode(root->left, key);
    } else {
        root->right = insertNode(root->right, key);
    }
    return root;
}

// Функция за намиране на минималния възел в дясното поддърво
Node* findMin(Node* root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

// Функция за изтриване на възел от дървото
Node* deleteNode(Node* root, int key) {
    if (root == NULL) {
        return root;
    }

    if (key < root->key) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->key) {
        root->right = deleteNode(root->right, key);
    } else {
        // Възел с един наследник или без наследници
        if (root->left == NULL) {
            Node* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == NULL) {
            Node* temp = root->left;
            delete root;
            return temp;
        }

        // Възел с два наследника
        Node* temp = findMin(root->right);
        root->key = temp->key;
        root->right = deleteNode(root->right, temp->key);
    }
    return root;
}

// Функция за принтиране на дървото (in-order)
void inorderPrint(Node* root) {
    if (root != NULL) {
        inorderPrint(root->left);
        cout << root->key << " ";
        inorderPrint(root->right);
    }
}

// Функция за преброяване на възлите с по един наследник
int countNodesWithOneChild(Node* root) {
    if (root == NULL) {
        return 0;
    }

    int count = 0;
    if ((root->left == NULL && root->right != NULL) || (root->left != NULL && root->right == NULL)) {
        count = 1;
    }

    return count + countNodesWithOneChild(root->left) + countNodesWithOneChild(root->right);
}

// Основно меню
void menu() {
    int choice, key;

    while (true) {
        cout << "\nМеню:\n";
        cout << "1. Добавяне на елемент\n";
        cout << "2. Изтриване на елемент\n";
        cout << "3. Принтиране на всички елементи\n";
        cout << "4. Преброяване на възлите с по един наследник\n";
        cout << "5. Изход\n";
        cout << "Вашият избор: ";
        cin >> choice;

        switch (choice) {
            case 1:
                cout << "Въведете ключ за добавяне: ";
                cin >> key;
                root = insertNode(root, key);
                break;
            case 2:
                cout << "Въведете ключ за изтриване: ";
                cin >> key;
                root = deleteNode(root, key);
                break;
            case 3:
                cout << "Елементите на дървото са: ";
                inorderPrint(root);
                cout << endl;
                break;
            case 4:
                cout << "Броят на възлите с по един наследник е: " << countNodesWithOneChild(root) << endl;
                break;
            case 5:
                return;
            default:
                cout << "Невалиден избор. Опитайте отново.\n";
        }
    }
}

int main() {
    menu();
    return 0;
}