When Android deletes a file, it doesn't just move it to a hidden folder. (That's what Windows does.) It actually marks the space that the file is sitting on as being unused. The data is still there (there's always data, even on a new, empty hard drive), but it's just about all marked as unused. When Android deletes a file it sets that space back as unused. If nothing gets stored in that space, the file can be recovered.
And there's a hole in the bucket, Dear Liza. (Name that singer.)