MadeEasy Test Series: Programming & DS - Binary Search Trees

Question

Q). Find the number of trees that are possible .If we construct a binary search tree by successively inserting $5$ distinct items int an initially empty tree.

a). $4$

b). $10$

c). $14$

d). $20$

I used the formula 2n!/(n+1)!*n!. Is it right ? also the ans given is 14,but I am getting 7.

Answer 1

no of BST=2nCn/n+1

               =10C5/6

               =42

Comments

thanks I will correct my formula, but why is the ans given 14?

---

in case of distinct elements, the total no of BST= catalan no. i.e. 2nCn/n+1 {actually asked in question}

and, the total no. of binary tree=  2n!/(n+1)!*n! [which you are using here]

so for 5 elements, no of BST= 42