If you delete a folder in QAComplete, the data in the folder is NOT deleted . The folder name is simply removed from the records, and you will find your records in the “root” section with no folder name. You will need to create/add the Folder again and after that you can use Fast Edit to move the records from one folder to another.
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.