sub f{($s,$t)=@_;{return$t if!$t||$t->{d}eq$s;$t=$t->{$t->{d}gt$s?l:r}
+;redo}}
[download]

...I think...

Very nice. I tried several times without success to come up with a good non-recursive solution. The above not only is short, but it really does the binary search, and applying standard golfing techniques, it comes up a winner at 55:

sub f{
($s,$t)=@_;$t=$$t{$$t{d}gt$s?l:r}while$t&&$$t{d}ne$s;$t
}
[download]

(Or 57 if you add my to kill side effects. Still better than anything I thought of.)

Note that this is much less readable than what tye wrote, but every transformation is fairly mechanical compression of the code...

Thanks, but credit goes to Masem for the algorithm as mine was just mechanical compression of Masem's original code. (:

        - tye (but my friends call me "Tye")

sub f{($s,$t)=@_;while($t->{d}ne$s){$t=$t->{(r,l)[$s lt$t->{d}]}||retu
+rn}$t}
[download]

sub f{($^,*_)=@_;*_=$_{(r,l)[$^lt$_{d}]}||return while$_{d}ne$^;*_}
[download]

Here's 58 chars with a completely different approach. .

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

--twerq

As koolade pointed out, not all of these work. Yours in particular goes into deep recursion. Works in theory is not good enough, in golf you are going to learn a lot about the assumptions you cannot make. And yours has at least 2 separate (and serious) mistakes.

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]

And here, thanks to koolade, is the test that I use:

$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]

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.

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

sub z{my($s,$t)=@_;return if!$t;(z($s,$t->{r},$t,z($s,$t->{l}))[$s cmp
+ $t->{d}]}
[download]