6
\$\begingroup\$

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)
\$\endgroup\$
7
\$\begingroup\$

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

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

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
\$\endgroup\$
  • \$\begingroup\$ Better yet, use math.factorial. The formula is \$\frac{(2n)!}{(n+1)!n!}\$. \$\endgroup\$ – kyrill Apr 22 '17 at 19:57
0
\$\begingroup\$

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]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.