## 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 givenn?

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

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…

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.

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

Blog post from a while back: http://grahamenos.com/stanley-catalan.html

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.

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

[…] our exercise a week ago, I’ve been reading about Catalan numbers, primarily based on the references at […]