No backup, no videos.... They are gone forever

 

Sadly I concur, if they were in the phone's internal storage.

If they were on a removable microSD card that had not been formatted as internal storage then no problem: remove it from the phone, stick it in a card reader, attach to a computer, run your favourite file recovery software. Job done. But if it was on the phone's storage, no. You may find someone pop up to recommend such-and-such "phone recovery" software, but I'm still waiting to see evidence of one of these things working that is clearly not coming from someone connected to the software developer.