How many distinct binary search trees can be created out of 4 distinct keys?a)4b)14c)24d)42Correct answer is option 'B'. Can you explain this answer?

Question

Answer

Number of Binary Search trees for n nodes is given by = (2n)! / n! * (n+1)!

Hence for 4 keys or nodes-

= 8! /4! * 5!

= 14

Hence, 14 distinct binary search trees are possible for 4 keys.

So, the Correct Answer is Option B

You can solve many such questions & mock tests by going through the course:

Mock Tests & Past Year Papers for CA Foundation

https://edurev.in/courses/16687_mock-tests--past-year-papers-for-ca-foundation

Answer

To determine the number of distinct binary search trees (BSTs) that can be created out of 4 distinct keys, we can use the concept of Catalan numbers.

Catalan numbers are a sequence of natural numbers that often appear in various combinatorial problems, including counting the number of BSTs. The formula to calculate the nth Catalan number is given by:

C(n) = (2n)! / ((n + 1)! * n!)

In this case, we want to find the number of distinct BSTs that can be created with 4 distinct keys. So, we substitute n = 4 into the formula:

C(4) = (2 * 4)! / ((4 + 1)! * 4!)

= 8! / (5! * 4!)

= (8 * 7 * 6 * 5!) / (5! * 4!)

= 8 * 7 * 6

= 336

However, this result includes all possible binary trees with 4 nodes, not just the distinct BSTs. The question specifically asks for the number of distinct BSTs.

To obtain the number of distinct BSTs, we need to divide the result by the number of possible arrangements of the same keys in a binary tree structure. For 4 distinct keys, there are 4! = 4 factorial = 4 * 3 * 2 * 1 = 24 possible arrangements.

Therefore, the number of distinct BSTs that can be created out of 4 distinct keys is:

336 / 24 = 14

So, the correct answer is option 'B' - 14.

Answer

14

Answer

Correct answer is option (B)

The maximum number of distinct binary search trees that can be formed with 'n' distinct keys is C(2n,n) / n+1.

Similar Computer Science Engineering (CSE) Doubts

How many distinct binary search trees can be created out of 4 distinct keys?

Which of the following is FALSE about B/B+ tree

We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree? (GATE CS 2011)

We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?

One of the uses of CNF is to turn parse tree into

Top Courses for Computer Science Engineering (CSE)View all

GATE Computer Science Engineering(CSE) 2026 Mock Test Series

Question Bank for GATE Computer Science Engineering

General Aptitude for GATE

Computer Networks

Programming and Data Structures

Top Courses for Computer Science Engineering (CSE)

Top Courses for Computer Science Engineering (CSE)

Related Content

Mock Test Series

Subject-wise Courses

Subject-wise Courses

Other Engg Branches

Company