"Deleted" for the most part just means it's unassociated with the previous markings/tables that define where things were stored. If you delete something, you have ways to retrieve it, be it via the Trash icon or third-party software.
"Overwritten" means that there has been something else put overtop of the old stuff, at that point, no, it's not recoverable. You've rewritten the same spot it *was* saved.
Only to add insult to injury, video files are usually large and when they play or get used they require their entire file or else they usually corrupt. How most hard drive disks save is fragmented. That means it's not always saved beside itself. If you as much saved a text file after losing your stuff, and that text file took up some of the space a video was, your video probably is corrupt. Corrupt videos don't usually play.
Sorry to be a baron of bad news, but better to have an answer than look for hours.