GATE Exam  >  GATE Questions  >  What is the maximum number of Binary Search T... Start Learning for Free
What is the maximum number of Binary Search Trees possible with 6 nodes?
  • a)
    130
  • b)
    132
  • c)
    135
  • d)
    137
Correct answer is option 'B'. Can you explain this answer?
Verified Answer
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
Most Upvoted Answer
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).
Explore Courses for GATE exam
What is the maximum number of Binary Search Trees possible with 6 nodes?a)130b)132c)135d)137Correct answer is option 'B'. Can you explain this answer?
Question Description
What is the maximum number of Binary Search Trees possible with 6 nodes?a)130b)132c)135d)137Correct answer is option 'B'. Can you explain this answer? for GATE 2024 is part of GATE preparation. The Question and answers have been prepared according to the GATE exam syllabus. Information about What is the maximum number of Binary Search Trees possible with 6 nodes?a)130b)132c)135d)137Correct answer is option 'B'. Can you explain this answer? covers all topics & solutions for GATE 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for What is the maximum number of Binary Search Trees possible with 6 nodes?a)130b)132c)135d)137Correct answer is option 'B'. Can you explain this answer?.
Solutions for What is the maximum number of Binary Search Trees possible with 6 nodes?a)130b)132c)135d)137Correct answer is option 'B'. Can you explain this answer? in English & in Hindi are available as part of our courses for GATE. Download more important topics, notes, lectures and mock test series for GATE Exam by signing up for free.
Here you can find the meaning of What is the maximum number of Binary Search Trees possible with 6 nodes?a)130b)132c)135d)137Correct answer is option 'B'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of What is the maximum number of Binary Search Trees possible with 6 nodes?a)130b)132c)135d)137Correct answer is option 'B'. Can you explain this answer?, a detailed solution for What is the maximum number of Binary Search Trees possible with 6 nodes?a)130b)132c)135d)137Correct answer is option 'B'. Can you explain this answer? has been provided alongside types of What is the maximum number of Binary Search Trees possible with 6 nodes?a)130b)132c)135d)137Correct answer is option 'B'. Can you explain this answer? theory, EduRev gives you an ample number of questions to practice What is the maximum number of Binary Search Trees possible with 6 nodes?a)130b)132c)135d)137Correct answer is option 'B'. Can you explain this answer? tests, examples and also practice GATE tests.
Explore Courses for GATE exam
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev