Approval Flow for deleting items

We have a SharePoint Online site, where users will be able to add/delete items to a Document Library. However we want to add an step so deletion actions gets approved before actually deleting the item (don't want to restore items from the recycle bin). Is this possible?

Unfortunatelly there is no trigger before file/item is deleted only when is already deleted. You could trigger Flow when item is deleted, request approval and if it is Rejected, find and restore the item from Recycle Bin using REST API.

Finding the right item in the Recycle Bin is a bit tricky, but it can be achieved.

The first(...) in the screenshot is: first(body('Parse_JSON')?['value'])?['Id']

Schema in Parse JSON action:

{
    "type": "object",
    "properties": {
        "odata.metadata": {
            "type": "string"
        },
        "value": {
            "type": "array",
            "items": {
                "type": "object",
                "properties": {
                    "odata.type": {
                        "type": "string"
                    },
                    "odata.id": {
                        "type": "string"
                    },
                    "odata.editLink": {
                        "type": "string"
                    },
                    "AuthorEmail": {
                        "type": "string"
                    },
                    "AuthorName": {
                        "type": "string"
                    },
                    "DeletedByEmail": {
                        "type": "string"
                    },
                    "DeletedByName": {
                        "type": "string"
                    },
                    "DeletedDate": {
                        "type": "string"
                    },
                    "DeletedDateLocalFormatted": {
                        "type": "string"
                    },
                    "DirName": {
                        "type": "string"
                    },
                    "DirNamePath": {
                        "type": "object",
                        "properties": {
                            "DecodedUrl": {
                                "type": "string"
                            }
                        }
                    },
                    "Id": {
                        "type": "string"
                    },
                    "ItemState": {
                        "type": "integer"
                    },
                    "ItemType": {
                        "type": "integer"
                    },
                    "LeafName": {
                        "type": "string"
                    },
                    "LeafNamePath": {
                        "type": "object",
                        "properties": {
                            "DecodedUrl": {
                                "type": "string"
                            }
                        }
                    },
                    "Size": {
                        "type": "string"
                    },
                    "Title": {
                        "type": "string"
                    }
                },
                "required": [
                    "odata.type",
                    "odata.id",
                    "odata.editLink",
                    "AuthorEmail",
                    "AuthorName",
                    "DeletedByEmail",
                    "DeletedByName",
                    "DeletedDate",
                    "DeletedDateLocalFormatted",
                    "DirName",
                    "DirNamePath",
                    "Id",
                    "ItemState",
                    "ItemType",
                    "LeafName",
                    "LeafNamePath",
                    "Size",
                    "Title"
                ]
            }
        }
    }
}