No of BST possible with n unlabelled nodes

Question

I was recently asked to tell the no of BST possible with n unlabelled nodes in an interview. But I couldn't understand the point of unlabelled nodes in BST and was not able to answer properly. What should be the appropriate answer to this question?

Answer 1

Indeed, I would also have expressed my surprise when presented with BSTs with unlabelled nodes. BSTs only make sense when nodes carry information.

I suppose they just meant binary trees. And for that counting problem you seem to have already answered the question by adding the catalan tag.

If we call C_n the number of binary trees that can be made with n nodes, then we can break the problem down to the possibilities for the subtrees of the root. First count the number of trees when all the non-root nodes are in the left subtree, then when one of them is actually in the right subtree, ...etc, and total all those counts.

• C₀ = 1
• C_n+1 = ∑_i=0..nC_i C_n-i

... and this is exactly the recurrence relation given for Catalan numbers.

And it is not hard to write this as a recursive function (pseudo code):

CountBT(n):
    if n == 0:
        return 1 
    total = 0
    for i = 0 to n:
        total = total + CountBT(i) * CountBT(n - i)
    return total

Using memoization this could be made more efficient.