With ' N ' no of nodes, how many different Binary and Binary Search Trees possible?

Question

For Binary trees: There's no need to consider tree node values, I am only interested in different tree topologies with 'N' nodes.

For Binary Search Tree: We have to consider tree node values.

Answer 1

1. Total no of Binary Trees are =

2. Summing over i gives the total number of binary search trees with n nodes.

The base case is t(0) = 1 and t(1) = 1, i.e. there is one empty BST and there is one BST with one node.

So, In general you can compute total no of Binary Search Trees using above formula. I was asked a question in Google interview related on this formula. Question was how many total no of Binary Search Trees are possible with 6 vertices. So Answer is t(6) = 132

I think that I gave you some idea...