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

Question

For Binary tree: You no need to consider tree node values, I am interested about different tree topologies with 'N' nodes.

For Binary Search Tree: We obviously consider tree node values.

Answer 1

Eric Lippert recently had a very in-depth series of blog posts about this: "Every Binary Tree There Is" and "Every Tree There Is" (plus some more after that).

In answer to your specific question, he says:

The number of binary trees with n nodes is given by the Catalan numbers, which have many interesting properties. The nth Catalan number is determined by the formula (2n)! / (n+1)!n!, which grows exponentially.

Answer 2

I recommend this article by my colleague Nick Parlante (from back when he was still at Stanford). The count of structurally different binary trees (problem 12) has a simple recursive solution (which in closed form ends up being the Catalan formula which @codeka's answer already mentioned).

I'm not sure how the number of structurally different binary search trees (BSTs for short) would differ from that of "plain" binary trees -- except that, if by "consider tree node values" you mean that each node may be e.g. any number compatible with the BST condition, then the number of different (but not all structurally different!-) BSTs is infinite. I doubt you mean that, so, please clarify what you do mean with an example!