Catalan Numbers

September 12, 2017

Today’s exercise is an Amazon interview question for software engineers and developers:

How many unique binary search trees can be made from a series of numbers 1, 2, 3, 4, …, n, for any given n?

Your task is to compute the number of unique binary search trees. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

7 Responses to “Catalan Numbers”

  1. Came up with the solution below… after looking at the graphs realised that

    Tn = Sum (0..n-1) T[i] T[n-i-1]
    {where T[0] = 1, T[1] = 1}

    e,g,
    T2 = T0T1 + T1T0
    T3 = T1T2 + T1T1 + T2T0

    Then came up with the following solution…

    my $N = shift;
    my @T = (1,1);
    
    foreach my $t (2..$N) {
      my $x = 0;
      $x += $T[$_] * $T[$t-$_-1] foreach 0 .. $t-1;
      push @T, $x;
    }
    shift @T;
    
    print join "\n", q(), @T, q(),q();
    
  2. Paul said

    A dynamic solution in Python (same method as @James Curtis-Smith). For n elements, you can split the range by taking out 1 element (the split). Then you have a number of elements at the left and a number on the right, so you can reduce the problem if you have calculated all case smaller than n already.

    def ntrees():
        table = [1]
        yield from table
        for k in count(1):
            table.append(sum(table[split] * table[k-1-split] for split in range(k)))
            yield table[-1]
    
  3. Forgot to say – the logic to the calculation is that you chose each element in turn for the fist element – other elements are either smaller larger than the current element {assuming no dupes}. We set the node as root and work out what trees are to the left or right…

    Smallest element:0 element tree to left : (n-1)-element tree to right – count is therefore T0 * T(n-1)
    Next element:1 element tree to left : (n-2)-element tree to right

    Next element:(n-1) element tree to left : 0 element tree to right- count is therefore T(n-1) * T0

  4. chaw said

    Once we map the problem to Catalan numbers (the title gives it away!)
    the main challenge may be calculating those numbers. The sample
    solution by @programmingpraxis works for modest values of n but for
    much larger values we can use the following, in standard (R7RS)
    Scheme. It runs in a few seconds with Larceny Scheme on my very modest
    computer.

    (import (scheme base)
            (scheme write))
    
    (define (n-choose-k/cps n k return)
      (if (zero? k)
          (return 1) 
          (n-choose-k/cps (- n 1)
                          (- k 1)
                          (lambda (result)
                            (return (* n
                                       (/ result k)))))))
    
    (define (n-choose-k n k)
      (call-with-current-continuation
       (lambda (cont)
         (n-choose-k/cps n k cont))))
    
    (define (cat-num n)
      (- (n-choose-k (* 2 n)
                     n)
         (n-choose-k (* 2 n)
                     (+ n 1))))
    
    (display  (cat-num 10000))
    (newline)
    

  5. Paul said

    A very fast way to calcuate Catalan numbers and a more elegant version of my earlier solution.

    def dotproduct(vec1, vec2):
        return sum(map(mul, vec1, vec2))
    
    def ntrees():
        table = [1]
        yield 1  # for n=0
        while True:
            table.append(dotproduct(table, reversed(table)))
            yield table[-1]
    
    def catalan_g():
        'very fast way to calculate Catalan numbers'
        yield from (0, 1)
        c = 1
        for n in count(1):
            c = c * 2 * (2*n + 1) // (n + 2)
            yield c
    
  6. […] our exercise a week ago, I’ve been reading about Catalan numbers, primarily based on the references at […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: