class Node
{
public:
    Node* left;
    Node* right;
    Node* parent;

    void setValue(int const value) noexcept
    {
        this->value = value;
    }

    inline int getValue() const noexcept
    {
        return value;
    }

    static Node* getLeafStarting(Node* start) noexcept
    {
        while(start->left != nullptr) {
            start = start->left;
        }

        if(start->right != nullptr) {
            return getLeafStarting(start->right);
        }

        return start;
    }

    static Node* removeNodes(Node* node, int value)
    {
        Node* current = node;

        bool hasLeft = current->left != nullptr;
        bool hasRight = current->right != nullptr;

        if(hasLeft) {
            removeNodes(current->left, value);
        }
        if(hasRight) {
            removeNodes(current->right, value);
        }

        if(!hasLeft && !hasRight && value == current->getValue()) {
            deleteNode(current);
        }
        else if((!hasLeft || !hasRight) && value == current->getValue()) {
            if(hasLeft) {
                current->left->parent = current->parent;
            }
            else if(hasRight) {
                current->right->parent = current->parent;
            }

            deleteNode(current);
        }
        else if(hasLeft && hasRight && value == current->getValue()) {
            auto leaf = getLeafStarting(current);

            leaf->parent = current->parent;
            leaf->left = current->left;
            leaf->right = current->right;

            deleteNode(current);
        }

        return node;
    }

private:
    int value;

    static void deleteNode(Node* node) noexcept
    {
        node->left = nullptr;
        node->right = nullptr;
        node->parent = nullptr;

        delete node;
    }
};