The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+12 votes
1.4k 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.4k points)
recategorized by | 1.4k views

2 Answers

+22 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 (9.2k points)
edited by
+1
Yes it will be equal to Catalan no.
+5
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?

+2 votes

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

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

35,487 questions
42,746 answers
121,455 comments
42,138 users