NO. OF BST POSSIBLE

Question

Comments

Is it 10?

---

there can be two possible cases:

1: make 5 as root

now u have ton fix 4 on the left of 5 to satisfy the required condition.

now you can make 5 bst using remaining 3 nodes.

{use formula-> no. of bst possible with n nodes= (2nCn)/(n+1)  }

2. second case make 4 as root ,and 5 as right of 4

now similliarly as the 1st case you can make 5 bst

hence ans will be 10.

Answer 1

We are given 5 nodes 1,2,3,4,5, we have to follow one rule here which is 1 should always be a child of 4(need not be immediate)

Firstly lets find out what is the root node of the tree among given numbers. We can see 1,2 and 3 can never be the root node  because if we make 1 as root (condition violated) and among 2 and 3 if any one of them is root node 1 and 4 will split into two different subtrees(conditon violated) and hence 1 can never become child of 4

Now we are left with 4 and 5 as root node which is possible according to our given condition.

Lets try with 4 as root node

Node 1,2,3 can be arranged in BST manner, no of ways are nothing but Catalan number= $\frac{C(2n,n)}{n+1}= \frac{C(6,3)}{4}= 5$

5 BST's are possible with 4 as root node.

Now we are left with 5 as root node

After 5 next root cannot be 1,2,3, reason is same as discussed above, hence 4 is next root node.

Again the same condition arises no of ways in which 1,2,3 can be arranged in BST =5

No. of BST with 4 as root node=5

No.of BST with 5 as root node=5.

Hence total number of BST possible=10

10 is the correct answer

Answer 2

It should be 10.