I haven't been able to get some of the answers to work. Maybe I have a different image of the data structure. Can somebody post what they've been working with?

Here's what I'm using to test:

$t = {
    d => 'd',
    l => {
        d => 'b',
        l => { d => 'a', l => 0, r => 0, },
        r => { d => 'c', l => 0, r => 0, },
    },
    r => {
        d => 'f',
        l => { d => 'e', l => 0, r => 0, },
        r => { d => 'g', l => 0, r => 0, },
    }
};
[download]

And here's a solution in 92 chars, that puts the tree into a single hash, and searches using the hash:

sub f{r(pop);$a{(pop)}||0;sub r{my$n=shift||return;$a{$n->{d}}=$n;r($n
+->{l});r($n->{r});};};
[download]

Speak up if I missed something.