What is the maximum number of Binary Search Trees possible with 6 node...
Number of BST with ‘n’ nodes is given by 2nCn/(n+1)
=>12C6/7 =132.
View all questions of this test
What is the maximum number of Binary Search Trees possible with 6 node...
To find the maximum number of Binary Search Trees (BSTs) possible with 6 nodes, we can use the concept of Catalan numbers. Catalan numbers are a sequence of natural numbers that occur in various counting problems, including counting the number of BSTs.
Understanding Catalan Numbers:
Catalan numbers can be defined recursively as follows:
- C(0) = 1 (base case)
- C(n) = sum(C(i) * C(n-i-1)) for i = 0 to n-1
Determining the Maximum Number of BSTs:
To find the maximum number of BSTs with 6 nodes, we need to calculate the Catalan number for n=6, i.e., C(6). Using the recursive formula mentioned above, we can compute C(6) as follows:
C(6) = C(0)*C(5) + C(1)*C(4) + C(2)*C(3) + C(3)*C(2) + C(4)*C(1) + C(5)*C(0)
Applying the recursive formula and substituting the base case values, we get:
C(6) = 1*C(5) + 1*C(4) + 2*C(3) + 5*C(2) + 14*C(1) + 42*C(0)
Now, we need to calculate the Catalan numbers for n=0 to n=5 to substitute in the above equation:
C(0) = 1
C(1) = C(0)*C(0) = 1*1 = 1
C(2) = C(0)*C(1) + C(1)*C(0) = 1*1 + 1*1 = 2
C(3) = C(0)*C(2) + C(1)*C(1) + C(2)*C(0) = 1*2 + 1*1 + 2*1 = 5
C(4) = C(0)*C(3) + C(1)*C(2) + C(2)*C(1) + C(3)*C(0) = 1*5 + 1*2 + 2*1 + 5*1 = 14
C(5) = C(0)*C(4) + C(1)*C(3) + C(2)*C(2) + C(3)*C(1) + C(4)*C(0) = 1*14 + 1*5 + 2*2 + 5*1 + 14*1 = 42
Substituting these values in the equation for C(6):
C(6) = 1*42 + 1*14 + 2*5 + 5*2 + 14*1 + 42*1
= 42 + 14 + 10 + 10 + 14 + 42
= 132
Therefore, the maximum number of BSTs possible with 6 nodes is 132 (option B).