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

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

    ///
    /// \brief Useful when you have to remove a node with two children.
    ///
    /// In this implementation we remove a node by taking a random leaf and
    /// putting it in the \p start's place.
    ///
    /// \param start Where to start looking for a leaf node.
    ///
    static Node* getLeafStarting(Node* start) noexcept
    {
        while(start->left != nullptr) {
            start = start->left;
        }

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

        return start;
    }

    ///
    /// \brief What should removing a node with 2 children mean? Is it a binary
    ///        search tree?
    ///
    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()) {
            node = current->parent;

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

            node = current->right;

            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;

            node = leaf;

            deleteNode(current);
        }

        return node;
    }

private:
    int value;

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

        delete node;
    }
};