Update 2: Compared to Eily's solution, mine is iterative (non recursive), while Eily's is recursive.

Yup, and my solution generates a lots of closures on the fly. This would probably make it slower on structures that are deeper than they are wide.

Your solution doesn't seem to work though, it goes down the levels alright, but never climbs back up. I'm afraid trying to work on this in an iterative way (I kind of see the idea, and I know it's possible) just confuses the perl out of me, so I can't point out what's wrong.