Compute the most efficient binary function
Haskell, 110 bytes

f q=head[i|let c=[(-1,0)]:[[(f a,f b)|n&lt;-[0..k],a&lt;-c!!n,b&lt;-c!!(k-n)]|k&lt;-[0..]],(p,i)&lt;-zip(concat c)[0..],p==q]


The argument here is taken to be the tuple (x,y). Pretty similar to the answer above, but the lookup list holds just the pairs of left and right indices instead of the trees.