Count number of ways to construct binary search tree with n elements

Question

I had this question asked in an interview:

In how many ways, we can construct binary search tree from \$n\$ elements?

I have written this code, but got a feedback that it could be improved. How to do it?

def count_ways(n):
    c = [0] * (n+1)
    c[0] = 1
    c[1] = 1
    for i in xrange(2, n+1):
        sum_w = 0
        for j in xrange(0, i):
            sum_w += c[j] * c[i-j-1]
        c[i] = sum_w
    return c[n]    


print count_ways(4)

Answer 1

The number of trees can be expressed in the closed form \$\frac{\binom{2n}{n}}{n+1}\$, and due to \$\binom{2n}{n} = \frac{4n - 6}{n} \binom{2(n-1)}{n-1}\$ the result is computed in linear time.

I would not ask such question in face-to-face interview (unless the position requires in-depth knowledge of combinatoric and graph theory).

Answer 2

The only optimization obvious to me is to reduce the number of iterations in the inner loop by the factor of two:

def count_ways_v2(n):
    c = [0] * (n + 1)
    c[0] = 1
    c[1] = 1
    for i in range(2, n + 1):
        sum_w = 0
        for j in xrange(0, i / 2):
            sum_w += 2 * c[j] * c[i - j- 1]
        if i % 2 == 1:
            sum_w += c[i / 2] * c[i / 2] # Handle the case in which i is odd:
        c[i] = sum_w
    return c[n]

Hope it helps.

Edit

@Peilonrayz suggests an improvement: your and mine versions run in quadratic time, yet via Catalan numbers you can do it in linear time:

def count_ways_catalan(n):
    a, b = 1, 1
    for k in range(2, n + 1):
        a *= n + k
        b *= k
    return a / b

Answer 3

Here is a slightly optimized version:

# python's default stack size is small
from sys import setrecursionlimit
setrecursionlimit((1<<31)-1)

def ways(n, cache={}):
    if n == 0: return 1
    elif n not in cache:
        cache[n] = sum(ways(s) * ways(n-s-1) for s in xrange(n))
    return cache[n]