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.