The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
1.5k 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.5k points)
edited by | 1.5k views

2 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?

+3 votes

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

answered by Loyal (6.6k 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

38,058 questions
45,554 answers
131,887 comments
48,909 users