Click here to Skip to main content
15,867,453 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
Suppose there are n elements in a list. I want to know that how many BSTs are possible with every possible subset of list. I have searched and catalan number is no the answer because it does not tell us about every subset.
Posted

1 solution

It looks like a school assignment, and the problem is not clearly and fully defined, so, sorry: no complete solution for you.

The question simply makes no full sense. List is irrelevant. If you select some subset of n < N elements, N becomes also irrelevant, only n is essential. The question is reduced to this one: given n objects, how many different binary search trees can be built from those elements? The hint: each particular tree instance depends on the element properties, ordering condition defined and order of feeding them into the algorithm populating the tree. Moreover, by apparent reasons, some orders of population will give identical trees, and some are different.

Now, how this question can be formulated as the algorithm question? Perhaps, the real problems is: how to create an algorithm for calculating all possible binary search trees generated by a given set of elements? This problem is simpler. You got some hints, not you can try to find a solution. How about trying it and asking more questions if you stuck?

—SA
 
Share this answer
 
Comments
Stefan_Lang 6-Jun-14 2:13am    
That's pretty much the best answer the OP can expect given the vagueness and generality of the question. Have a 5!
Sergey Alexandrovich Kryukov 6-Jun-14 2:22am    
Thank you, Stefan.
—SA

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900