Recovering deleted videos on android that were never saved to Google

Hi All. I'm hoping someone can help me as I've looked on this board and can't find my issue.

I accidentally deleted a video from my old amsung galaxy so edge phone 2 years ago. I deleted it before it was backed up to Google. I went through a host of freeware to try recover it and then paid for data recovery package on dr.fone, but nothing. To use this software I had to root the device.

After this I just gave up and continued on using the phone for about another year, and I assume the sectors have been written over. But a friend recommend that I ask you guys if there is any other software out there that allows me to look deeper on the internal storage?

Any help or advise is greatly appreciated. Thanks in advance folks.
Paul