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

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)


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

• Nice! Do you have a link to the explanation of the closed form? – janos Apr 23 '17 at 5:40

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 (see his link) 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

• Better yet, use math.factorial. The formula is $\frac{(2n)!}{(n+1)!n!}$. – kyrill Apr 22 '17 at 19:57

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]