If the videos were on a microSD card (not all phones use them) it should not be possible to get them back. First, DO NOT WRITE ANYTHING ELSE TO THE CARD. The safest thing to do is remove the card from the phone. Then, do a search for file recovery utilities. There are a ton of them available. Choose one from a reputable site.
If the videos were stored on the phones built in memory it may be possible to recover the videos but it is more likely the deleted files were overwritten and there is a possibility of corrupting the phone with the recovery utilities.
Tar, feathers, congress. Some assembly required.