How to do question 7

#1

how to do question 7 in quiz of bst

#2

hi @akshatkaush,
for this you need to know about catalan number , no of BST=catalan(n) ,no of BS=catalan(n)*n!
where catalan(n) = (2n)! / ((n + 1)! * n!)
catalan(n) is obtained from the recursive relation T(N) = summation k from 0 to (N-1)(T(k)*T(N-1-k)
which is same for no of bst for n nodes

to solve recursive relation you need to have knowledge about generating functions which would be little too much for u to know , so i will suggest to remember catalan number and the recursive relation
Catalan numbers are a sequence of natural numbers that occurs in many interesting counting problems like following mentioned .

  1. Count the number of expressions containing n pairs of parentheses which are correctly matched. For n = 3, possible expressions are ((())), ()(()), ()()(), (())(), (()()).

  2. Count the number of possible Binary Search Trees with n keys

  3. Count the number of full binary trees (A rooted binary tree is full if every vertex has either two children or no children) with n+1 leaves.

1 Like
#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.