struct Node
{
    int value;
    Node *left;
    Node *right;
};

Node *tree_delete(Node **root, Node *removeElement)
{
    // we look at three cases:
    //  1 - no children
    //  2 - one child
    //  3 - two children (replace with successor)

    Node *replacementNode = nullptr;
    Node *x = nullptr;

    if (removeElement->left == nullptr || removeElement->right == nullptr)
    {
        // case no children or 1 child
        replacementNode = removeElement;
    }
    else
    {
        replacementNode = tree_successor(removeElement);
    }

    if (replacementNode->left != nullptr)
    {
        x = replacementNode->left;
    }
    else
    {
        x = replacementNode->right;
    }

    if (x != nullptr)
    {
        x->parent = replacementNode->parent;
    }

    if (replacementNode->parent == nullptr)
    {
        *root = replacementNode;
    }
    else if (replacementNode == replacementNode->parent->left)
    {
        replacementNode->parent->left = x;
    }
    else
    {
        replacementNode->parent->right = x;
    }

    if (replacementNode != removeElement)
    {
        removeElement->value = replacementNode->value;
    }

    return y;
}


Node *tree_successor(Node *node)
{
    if (node->right != nullptr)
    {
        return min_tree_search(node->right);
    }

    Node *tmpParent = node->parent;
    while (tmpParent != nullptr && node = tmpParent->right)
    {
        tmpParent = node->parent;
    }

    return tmpParent;
}

Node *min_tree_search(Node *node)
{
    while (node->left == nullptr) return node;
    return min_tree_search(node->left);
}