BTW the counts as I list them are just for the body of the sub, so if yours did work it would be 51 characters.

Playing independently I came in with several solutions that are small, and the following which is similar to yours really does work at 58:

sub f {
my($s,$t)=@_;$t?$$t{d}eq$s?$t:f($s,$$t{l})||f($s,$$t{r}):0
}
[download]

$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, },
    }
};

sub test {
  my $val = f(@_);
  print $val ? "$val->{d}:$val\n" : "$val\n";
}

test('e',$t);
test('O',$t);
[download]

Both tilly and indigo have exactly the same result, which is a fix of twerq's including 1) my, and 2) the test for $t which prevents infinite looping.

Here is a solution which is short, but not 'strict' compliant: sub f{for(($s,$t)=@_;$_=$$t{(0,l,r)[$$t{d}cmp$s]};$t=$_){}$t} Alas, although 4 characters lighter, it doesn't return 0 on misses properly. This does, but is admittedly 3 characters heavy: sub f{for(($s,$t)=@_;$_=$t&&(0,l,r)[$$t{d}cmp$s];){$t=$$t{$_}||0}$t} Or, a tie, provided the tree has 0-value stubs as it does in other examples: sub f{for(($s,$t)=@_;$_=$t&&(0,l,r)[$$t{d}cmp$s];){$t=$$t{$_}}$t} Fun test code below for a tree:

    $|++;
    $table = {
        d => 'h',
        l => {
             d => 'd',
             l => { d => 'b', l => { d => 'a' }, r => { d => 'c' } },
             r => { d => 'f', l => { d => 'e' }, r => { d => 'g' } },
        },
        r => {
             d => 'l',
             l => { d => 'j', l => { d => 'i' }, r => { d => 'k' } },
             r => { d => 'm', l => { d => 'l' }, r => { d => 'n' } },
        }
    };

    foreach $y (qw[ a b c d e f g h i j k l m n o p q ])
    {
            $x = f($y,$table);
            print "Answer for $y = ";
            print $x," ", $$x{d},"\n";
    }
[download]

value entry in the hash.

Well it has to handle both failure and success. However by borrowing shamelessly from tye, I beat my previous, and if we want to be shamelessly non-strict about it, I can improve again.

sub f {
$t=pop;$t=$$t{$c>0?l:r}while$c=$$t{d}cmp$_[0]and$t;$t
}
[download]

By my count this is 53 characters.