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).

• janos: Nice! Do you have a link to the explanation of the closed form?

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

• kyrill: Better yet, use math.factorial. The formula is \$\frac{(2n)!}{(n+1)!n!}\$.

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]