The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
1.6k views

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

  1. $5$
  2. $14$
  3. $24$
  4. $42$
asked in Graph Theory by Veteran (59.6k points)
edited by | 1.6k views

3 Answers

+23 votes
Best answer

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.

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

answered by Loyal (9k points)
edited by
+2
Yes it will be equal to Catalan no.
+6
0
sir distinct keys does not mean labelled nodes?
+1

no because distinct keys in BST must satisfy a property. while in a labelled nodes binary tree there is  no such restriction 

0
@Arjun sir

Distinct  Key  BST and Unlabeled node  BST Both are same and It is equal to Catalan Number?
0

Lakshman Patel RJIT  yes try creating distinct binary trees with 3 unlabeled nodes and also try creating BST's with keys {1,2,3} and it is unlabeled Binary tree not unlabeled BST

0

@Mk Utkarsh I'm little bit confuse

can you explain?

0
$\text{No. of BST with n nodes}$=$\sum_{i=1}^{n} T(i-1)*T(n-i)$ $\text{where}  $ $ T(0)=T(1)=1$
+3 votes

Number of binary trees with n-vertices =2n!/n!(n+1)! =14 so option B is answer

answered by Loyal (6.9k points)
0 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)

 

answered by Boss (20.2k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,992 questions
47,620 answers
146,892 comments
62,346 users