89

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.

Improve this question

11 Answers 11

Reset to default
90

  1. Total no of Binary Trees are = enter image description![enter image description here

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

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. enter image description here

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

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Note that 1 and 2 are actually different ways of expressing the same formula, not formulas for different quantities, in case that wasn't clear.
@Black_Rider - I tried the above formula to calculate the no. of possible trees for 100 unique nodes. But it is failing. I used DP to solve the problem. You can find the code here. The answer is wrong. Expected answer is 25666077 but actual output is 7159379471982673992. Could you help me on this?
What if some trees have the same keys? For example for tree 1, 1, 2, 2 it's not possible to squeeze similar keys to one vertex
49

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.

Final Formula

Improve this answer

Comments

44

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!

Improve this answer

3 Comments

the solution provided here cslibrary.stanford.edu/110/BinaryTrees.html # 12 doesn't match the solution provided by calculated by catalan number. That is countTrees(4) should be 5 not 14, right? But it returns 14. (This is the series 1, 1, 2, 5, 14, 42, 132)
countTrees(4) is the 5th element in the series as the series starts from 0 and that is what it returned: 14
I would recommend this graphic tutorial on catalan numbers by Indian Institute of Technology Ropar youtube.com/watch?v=BLG9E_PoXXc&feature=emb_logo.
17

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)

Improve this answer

1 Comment

nice simplification
11

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.

Improve this answer

1 Comment

The nth Catalan number formula (2n)! / (n+1)!n! grows exponentially. How do we write an algorithm to solve this for n > 11 ?
7

Different binary trees with n nodes:

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

where C=combination eg.

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

Comments

5 
(2n)!/n!*(n+1)!
Improve this answer

Comments

2

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

Improve this answer

Comments

1 
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
Improve this answer

Comments

1

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

Improve this answer

Comments

1

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

Improve this answer

1 Comment

Can you explain the 2nCn and (n+1) in the first formula?

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.