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...

Answer 2

The number of binary trees can be calculated using the catalan number.

The number of binary search trees can be seen as a recursive solution. i.e., Number of binary search trees = (Number of Left binary search sub-trees) * (Number of Right binary search sub-trees) * (Ways to choose the root)

In a BST, only the relative ordering between the elements matter. So, without any loss on generality, we can assume the distinct elements in the tree are 1, 2, 3, 4, ...., n. Also, let the number of BST be represented by f(n) for n elements.

Now we have the multiple cases for choosing the root.

1. choose 1 as root, no element can be inserted on the left sub-tree. n-1 elements will be inserted on the right sub-tree.
2. Choose 2 as root, 1 element can be inserted on the left sub-tree. n-2 elements can be inserted on the right sub-tree.
3. Choose 3 as root, 2 element can be inserted on the left sub-tree. n-3 elements can be inserted on the right sub-tree.

...... Similarly, for i-th element as the root, i-1 elements can be on the left and n-i on the right.

These sub-trees are itself BST, thus, we can summarize the formula as:

f(n) = f(0)f(n-1) + f(1)f(n-2) + .......... + f(n-1)f(0)

Base cases, f(0) = 1, as there is exactly 1 way to make a BST with 0 nodes. f(1) = 1, as there is exactly 1 way to make a BST with 1 node.

Answer 3

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!

Answer 4

If given no. of Nodes are N Then.

Different No. of BST=Catalan(N)
Different No. of Structurally Different Binary trees are = Catalan(N)

Different No. of Binary Trees are=N!*Catalan(N)

Answer 5

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 6

Different binary trees with n nodes:

(1/(n+1))*(2nCn)

where C=combination eg.

n=6,
possible binary trees=(1/7)*(12C6)=132

Answer 7

(2n)!/n!*(n+1)!

Answer 8

The number of possible binary search tree with n nodes (elements,items) is

=(2n C n) / (n+1) = ( factorial (2n) / factorial (n) * factorial (2n - n) ) / ( n + 1 ) 

where 'n' is number of nodes  (elements,items ) 

Example :

for 
n=1 BST=1,
n=2 BST 2,
n=3 BST=5,
n=4 BST=14 etc

Answer 9

binary tree :

No need to consider values, we need to look at the structrue.

Given by (2 power n) - n

Eg: for three nodes it is (2 power 3) -3 = 8-3 = 5 different structrues

binary search tree:

We need to consider even the node values. We call it as Catalan Number

Given by 2n C n / n+1

Answer 10

The correct answer should be 2nCn/(n+1) for unlabelled nodes and if the nodes are labelled then (2nCn)*n!/(n+1).

Answer 11

• Total number of possible Binary Search Trees with n different keys = 2nCn / (n + 1)
  

  For n = 1  --> 1 Binary Search Tree is possible.
  For n = 2  --> 2 Binary Search Trees are possible.
  For n = 3  --> 5 Binary Search Trees are possible.
  For n = 4  --> 14 Binary Search Trees are possible.
  For n = 5  --> 42 Binary Search Trees are possible.
  For n = 6  --> 132 Binary Search Trees are possible.```
  
  

• And Total number of possible Binary Trees with n different keys = (2nCn / (n + 1)) * n!
  

  For n = 4 --> 336 Binary Search Trees are possible.