We should support searching for deleted files in a specific path. On FAT systems this will speed things up immensely.
For NTFS, we'll have to implement a traversal to the root (using parent pointers) to get the path of each MFT record. Hopefully this doesn't slow things down too much. Once we have this information, we can have a tree view (tabbed with the list view) so that users can explore the deleted files by location.