// Error a propósito: en el borrado con dos hijos, se copia la clave del sucesor
// y se olvida borrar el nodo del sucesor. check_invariants lo descubre.
#include <cassert>
#include <cstddef>
#include <iostream>

class BrokenSet {
    struct Node {
        int key;
        Node* left = nullptr;
        Node* right = nullptr;
    };

public:
    BrokenSet() = default;
    BrokenSet(const BrokenSet&) = delete;
    BrokenSet& operator=(const BrokenSet&) = delete;
    ~BrokenSet() { destroy(root_); }

    void insert(int key) {
        Node** link = &root_;
        while (*link != nullptr) {
            link = key < (*link)->key ? &(*link)->left : &(*link)->right;
        }
        *link = new Node{key};
        size_++;
    }

    void erase_two_children(int key) {
        Node* node = root_;
        while (node->key != key) {
            node = key < node->key ? node->left : node->right;
        }
        Node* next = node->right;
        while (next->left != nullptr) {
            next = next->left;
        }
        node->key = next->key;
        size_--;
        // Falta quitar next del árbol: su clave quedó dos veces.
    }

    void print_in_order() const {
        print(root_);
        std::cout << std::endl;
    }

    void check_invariants() const {
        assert(count_checked(root_, nullptr, nullptr) == size_);
    }

private:
    static void destroy(Node* node) {
        if (node != nullptr) {
            destroy(node->left);
            destroy(node->right);
            delete node;
        }
    }

    static void print(const Node* node) {
        if (node != nullptr) {
            print(node->left);
            std::cout << node->key << " ";
            print(node->right);
        }
    }

    static std::size_t count_checked(const Node* node, const int* low, const int* high) {
        if (node == nullptr) {
            return 0;
        }
        assert(low == nullptr || *low < node->key);
        assert(high == nullptr || node->key < *high);
        return 1 + count_checked(node->left, low, &node->key)
                 + count_checked(node->right, &node->key, high);
    }

    Node* root_ = nullptr;
    std::size_t size_ = 0;
};

int main() {
    BrokenSet tree;
    for (int key : {5, 3, 8, 1, 4, 7}) {
        tree.insert(key);
    }
    tree.erase_two_children(5);
    tree.print_in_order();
    tree.check_invariants();
    return 0;
}