recategorized by
24,245 views
31 votes
31 votes

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

  1. $5$
  2. $14$
  3. $24$
  4. $42$
recategorized by

4 Answers

Best answer
39 votes
39 votes

answer - (B)

number of distinct BSTs = $\frac{^{2n}C_n}{n+1}$ (or) =$\frac{(2n)!}{(n+1)!n!}$

For a given Binary tree structure, there can be only $1$ BST. Hence, no. of different BSTs with $n$ nodes will be equal to the no. of different binary tree structures possible for $n$ nodes assuming nodes are unlabeled.

For derivation:
http://gatecse.in/number-of-binary-trees-possible-with-n-nodes/

edited by
5 votes
5 votes
Number of binary trees with unlabeled $n-vertices $
$T(n) = T(0)\times T(n-1)+T(1)\times T(n-2)+ \space ... \space+  T(n-1)\times T(0)$

$T(0)=T(1)=1$

$T(4) = T(0)\times T(3) + T(1)\times T(2) + T(2)\times T(1) + T(3)\times T(0)   \rightarrow$ eqn #1

$T(2) = T(0)\times T(1) + T(1)\times T(0) = 2$

$T(3) = T(0)\times T(2) + T(1)\times T(1) + T(2)\times T(0) = 2+1+2 = 5$

Just put values in eqn #1

$T(4)=5+2+2+5=14$
edited by
3 votes
3 votes

Incase you forgot the formula,

Number of BST's with 2 keys (1,2) = 2

Number of BST's with 3 keys (1,2,3) = 2 + 2 + 1 = (Root is 3) + (Root is 1)  +  (Root is 2)  = 5

Number of BST's with 4 keys (1,2,3,4) = 5 + 5 + 2 + 2 = 14 

Number of BST's with 5 keys (1,2,3,4,5) = 14 + 14 + 5 + 5 + 2 * 2 = 42

Number of BST's with 5 keys (1,2,3,4,5) = Root 5 + Root 1 + Root 4 + Root 2 + Root 3 (2 trees with 2 keys on either side)

 

1 votes
1 votes

In general the BST is of the form     

 i.e. 1 node at root, 2 its children, another 4 as its children and so on.

                      

Hence for root=   4C1

for the next two children= 3C2

 and the next= 1C1

also we will add the 2 skew trees

thus total BST=  4C1 * 3C2 * 1C1    2 = 14 trees

Answer:

Related questions

22 votes
22 votes
3 answers
1
22 votes
22 votes
8 answers
2
Kathleen asked Sep 22, 2014
22,974 views
In a complete $k$-ary tree, every internal node has exactly $k$ children. The number of leaves in such a tree with $n$ internal node is:$nk$$(n-1)k + 1$$n(k-1) +1$$n(k-1)...
20 votes
20 votes
1 answer
3
Kathleen asked Sep 22, 2014
13,935 views
A priority queue is implemented as a Max-Heap. Initially, it has $5$ elements. The level-order traversal of the heap is: $10, 8, 5, 3, 2$. Two new elements $1$ and $7$ ar...
43 votes
43 votes
8 answers
4
Kathleen asked Sep 22, 2014
19,328 views
An Abstract Data Type (ADT) is:same as an abstract classa data type that cannot be instantiateda data type for which only the operations defined on it can be used, but no...