How do you restore a deleted Folder and the Test Cases that were in it?

If you 'removed' the files in TestComplete and the files are still on disk, then you can Add them back as an Existing Item.  If you 'deleted' the files (and they are gone from disk), then you retrieve them from the backups that you have been faithfully maintaining and Add them back.

Note that 'Folders' in the Project Explorer view are logical constructs.  You won't find a folder on disk.  When you add back the missing tests, you'll have to recreate the folders in your TestComplete project.