When an e-mail is deleted, it is not deleted immediately. Instead, it is moved to the Deleted Items folder. If you want to recover the mail, you can go to the Deleted Items folder and move the mail back.

If necessary, click the View menu and select Folder List to show your folders. Then click on the Deleted Items folder and right-click the objects that you would like to recover. Now click Move to Folder....

Indicate which folder you would like the recovered E-mail to be sent to, and click OK.