I thought this was going to be a tricky one, but it turned out to be quite easy thanks to Google (and [this articlehttps://support.office.com/en-us/article/Recover-a-deleted-contact-in-Outlook-51c83288-6888-4dcd-8c99-4932daabf643?ui=en-US&rs=en-US&ad=US])
Deleted contacts go into the "Deleted items" folder like anything else that is deleted. Once we went into the deleted items folder and found the deleted contact (we ordered the list by "type" ), we then just drag-n-dropped it back into the contacts folder.
In order to see the contact folders we had to change the view on the left column to "folder list"