---

#include <iostream>

struct ttree {
    int inf;
    ttree *left, *right;
};

// Добавление элемента
ttree* addtree(ttree *proot, int inf) {
    ttree *nl = new ttree{inf, NULL, NULL};
    if (proot == NULL) return nl;
    ttree *ps = proot, *pr;
    bool b;
    while (ps != NULL) {
        pr = ps;
        b = (inf < ps->inf);
        if (b) ps = ps->left;
        else ps = ps->right;
    }
    if (b) pr->left = nl;
    else pr->right = nl;
    return proot;
}

// Поиск узла и его родителя
ttree* findParent(ttree* root, int key, ttree** parent) {
    ttree* cur = root;
    *parent = NULL;
    while (cur && cur->inf != key) {
        *parent = cur;
        if (key < cur->inf) cur = cur->left;
        else cur = cur->right;
    }
    return cur;
}

// Удаление поддерева
void delSub(ttree* node) {
    if (!node) return;
    delSub(node->left);
    delSub(node->right);
    delete node;
}

// Удаление ветви по ключу (задание 3)
ttree* deleteBranch(ttree* root, int key) {
    ttree *par, *tgt = findParent(root, key, &par);
    if (!tgt) { std::cout << "Не найден\n"; return root; }
    if (!par) { delSub(tgt); return NULL; }
    if (par->left == tgt) par->left = NULL;
    else par->right = NULL;
    delSub(tgt);
    std::cout << "Ветвь с ключом " << key << " удалена\n";
    return root;
}

// Вывод дерева (для проверки)
void print(ttree* p) {
    if (!p) return;
    print(p->left);
    std::cout << p->inf << " ";
    print(p->right);
}

int main() {
    setlocale(LC_ALL, "Russian");
    ttree *root = NULL;
    
    // Создаём одну правую ветвь: 1 → 2 → 3 → ... → 10
    for (int i = 1; i <= 10; i++)
        root = addtree(root, i);

    std::cout << "Дерево: ";
    print(root);
    std::cout << "\nВведите ключ для удаления ветви: ";
    
    int key;
    std::cin >> key;
    root = deleteBranch(root, key);
    
    std::cout << "Итог: ";
    print(root);

    return 0;
}