Just to get things started...

However I'm definitely not proud of this code. Whitespace has not been taken out for clarity.

The function basically outputs the worst possible tree after sorting the array, each left leaf is always 0 and the right is built iteratively, thus not using recursion. Since building strings is much easier than building trees (no pun intended), I did exactly that, evalling the result. It is a hash, not a reference, as the example code seems to suggest. Outputting a ref would allow some more savings :-)

Warning: for $func to work properly with sort, it should be prototyped:
my $func = sub($$) { $_[0] <=> $_[1] };

And now the code: 

sub buildtree {
        my($f, @a) = @_;
        local $_;

        @a = ((sort $f @a), '');
        $_ = join '=>[0,{', @a;
        chop;
        $_ = '(' . $_ . '0' . ']}' x $#a;
        s/}$/)/;
        eval;
}

[download]

It should be 103 chars excluding function declaration and non significative whitespace.

It can be tested in this context:

#!/usr/bin/perl -w

use strict;
use Data::Dumper;

sub buildtree {
        my($f, @a) = @_;
        local $_;

        @a = ((sort $f @a), '');
        $_ = join '=>[0,{', @a;
        chop;
        $_ = '(' . $_ . '0' . ']}' x $#a;
        s/}$/)/;
        eval;
}

my @array = ( 6, 1, 2, 3, 4, 5 );
my $func = sub($$) { $_[0] <=> $_[1] };

my %tree = buildtree( $func, @array );

print Dumper \%tree;

[download]

Update: In the initial post I forgot to add the character count :-)

Update 2: After tilly's comment I changed the function so that there's no need to prototypes, and I took some time to compress it further down to 88 chars: 

        #        1         2         3         4
        #23456789012345678901234567890123456789012345
        my$f=shift;@_=((sort{&$f($a,$b)}@_),'');$_=
        join'=>[0,{',@_;chop;%{eval"{$_ 0".']}'x$#_};

[download]

-- TMTOWTDI

In reply to Re: (Golf) Building a Better Binary Tree by trantor
in thread (Golf) Building a Better Binary Tree by Masem

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.