158 characters, avoiding the recursive answer. 
$f=shift;$h->{pop@_}=[0,0];for(@_){$i=$h;for(;;){$s=(keys%$i)[0];$b=($
+f->($_,$s)||last)>0?1:0;$i->{$s}[$b]?$i=$i->{$s}[$b]:($i->{$s}[$b]={$
+_,[0,0]},last)}}%$h

[download]
If handed a sorted array, it builds the worst-possible, cause it chooses the last element as the root. However, if handed an unsorted array, it should be relatively nice.

Update: After thinking about this for a while, I cut it down a bit, down to 148 characters.

Update2: 144 after removing unnecessary parens and rearranging the assignment to $h and rearranging the inner for-loop. 

$f=shift;$h={pop@_,[0,0]};for(@_){for($i=$h;;){$s=(keys%$i)[0];$b=($f-
+>($_,$s)||last)>0?1:0;$i=$i->{$s}[$b]||($i->{$s}[$b]={$_,[0,0]},last)
+}}%$h

[download]

Update3: By doing some horrible rearranging in the inner for-loop declaration, I cut to 142. *shudders*

Update4: After reading jynx's post, I cut the @_ in the assignment to $h. Now 139 characters. 

$f=shift;$h={pop,[0,0]};for(@_){for($i=$h;$s=(keys%$i)[0];$i=$i->{$s}[
+$b]||($i->{$s}[$b]={$_,[0,0]},last)){$b=(&$f($_,$s)||last)>0?1:0}}%$h

[download]

Update5: I promise this is the last! :-) 136 characters, after removing all hashrefs. 

$f=shift;%h=(pop,[0,0]);for(@_){for(%i=%h;$s=(keys%i)[0];%i=%{$i{$s}[$
+b]||($i{$s}[$b]={$_,[0,0]},last)}){$b=(&$f($_,$s)||last)>0?1:0}}%h

[download]

Update6: I lied. *sighs* 130 characters by adding variable aliasing. 

$f=shift;%h=(pop,[0,0]);for$c(@_){for(%i=%h;$s=(keys%i)[0];){%i=%{$_||
+($_={$c,[0,0]},last)}for$i{$s}[(&$f($c,$s)||last)>0?1:0]}}%h

[download]

------
We are the carpenters and bricklayers of the Information Age.

Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.

In reply to Re: (Golf) Building a Better Binary Tree by dragonchild
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.