Compute the most efficient binary function

Haskell, 110 bytes

f q=head[i|let c=[(-1,0)]:[[(f a,f b)|n<-[0..k],a<-c!!n,b<-c!!(k-n)]|k<-[0..]],(p,i)<-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.

Wow! I actually managed to make an efficient computation algorithm. I did not expect this at first. The solution is quite elegant. It repeatedly deduces more and more, then recurses all the way down to the base case of 0. In this answer the C(n) function denotes the Catalan numbers.

The crucial first step is acknowledging that there are C(0) = 1 values of length zero (namely 0 itself), C(1) = 1 values of length one (namely f(0, 0)), C(2) = 2 values of length two (f(0, f(0, 0)) and f(f(0, 0), 0)).

This means that if we're looking for the nth expression, and we find the biggest k such that C(0) + C(1) + ... + C(k) <= n then we know that n has length k.

But now we can continue! Because the expression we look for is the n - C(0) - C(1) - ... - C(k) th expression in its length class.

Now we can use a similar trick to find the length of the left segment, and then the rank within that subsection. And then recurse on those ranks we found!

It found that f(5030, 3749) = 1542317211 in the blink of an eye.

Python, noncompeting

def C(n):
    r = 1
    for i in range(n):
        r *= 2*n - i
        r //= i + 1
    return r//(n+1)

def unrank(n):
    if n == 0: return 0

    l = 0
    while C(l) <= n:
        n -= C(l)
        l += 1

    right_l = l - 1
    while right_l and n >= C(l - 1 - right_l) * C(right_l):
        n -= C(l - 1 - right_l) * C(right_l)
        right_l -= 1

    right_num = C(right_l)

    r_rank = n % right_num
    l_rank = n // right_num

    for sz in range(l - 1 - right_l): l_rank += C(sz)
    for sz in range(right_l): r_rank += C(sz)

    return (unrank(l_rank), unrank(r_rank))

def rank(e):
    if e == 0: return 0
    left, right = e

    l = str(e).count("(")
    left_l = str(left).count("(")
    right_l = str(right).count("(")
    right_num = C(right_l)

    n = sum(C(sz) for sz in range(l))
    n += sum(C(sz)*C(l - 1 - sz) for sz in range(left_l))

    n += (rank(left) - sum(C(sz) for sz in range(left_l))) * C(right_l)
    n += rank(right) - sum(C(sz) for sz in range(right_l))

    return n

def f(x, y):
    return rank((unrank(x), unrank(y)))

I'm fairly certain I'm doing a bunch of unnecessary computation and a lot of middle steps could be removed.

Python 3, 154 bytes

b=lambda n:[(l,r)for k in range(1,n)for l in b(k)for r in b(n-k)]+[0]*(n<2)
def f(x,y):r=sum((b(n)for n in range(1,x+y+3)),[]);return r.index((r[x],r[y]))

It's not very fast nor very golfy, but it's a start.