The Gateway to Computer Science Excellence
+2 votes
Let us there are n nodes which are labelled.

Then the number of trees possible is given by the Catalan Number i.e $\binom{2n}{n} / (n+1)$

Then the binary search trees possible is just 1?
in DS by | 932 views
For a given unlabeled tree, there is only 1 way a BST can be formed.

For n labeled nodes, Catalan Number of BST can be formed.
Hi the language of the question is pretty vague, please copy and paste the exact question.

3 Answers

+1 vote
For example, if number of nodes are 3 then 5 unlabelled binary trees[2nCn/(n+1)] are possible with 3 nodes. So, for each unlabelled binary tree there are 6 possible labelled binary trees[(i.e.,n!,(3!=3*2*1)] . Suppose that 3 labelled nodes are 1,2,3 and assume that the inorder traversal for this labelled binary tree is 123, then among those 6 possible binary trees you can get only one binary search tree as inorder 123.
edited by
0 votes
catalan number. for N labelled nodes, the nos of Binary Search Trees is catalan number.
0 votes
According to given in CLRS the total number of Binary Search tree is itself the catalan number

(2n C n) /(n+1)
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
52,315 questions
60,430 answers
95,244 users