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.

score 90 · Answer 1 · edited Oct 17 '12 at 15:53

90

Total no of Binary Trees are =
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. 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...

edited Oct 17 '12 at 15:53

Sankalp

1,128
4
14
31

answered Sep 21 '12 at 13:57

Black_Rider

1,465
2
16
18

7

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. – Todd O'Bryan Oct 30 '13 at 03:11
1

@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](https://github.com/dineshappavoo/ctgi/blob/master/src/com/ctgi/google/problems/MaximumPossibleWaysOfBST.java). The answer is wrong. Expected answer is 25666077 but actual output is 7159379471982673992. Could you help me on this? – Dany Apr 17 '15 at 06:51
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 – Evgeny Nov 21 '19 at 08:37

score 47 · Answer 2 · edited Jul 02 '14 at 15:08

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.

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

score 44 · Accepted Answer · answered Jun 15 '10 at 04:02

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!

answered Jun 15 '10 at 04:02

Alex Martelli

854,459
170
1,222
1,395

1

the solution provided here http://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) – Joyce Feb 15 '16 at 17:19
1

countTrees(4) is the 5th element in the series as the series starts from 0 and that is what it returned: 14 – Erric Jun 17 '17 at 20:58
I would recommend this graphic tutorial on catalan numbers by Indian Institute of Technology Ropar https://www.youtube.com/watch?v=BLG9E_PoXXc&feature=emb_logo. – angshuk nag Dec 08 '20 at 14:27

score 15 · Answer 4 · answered Oct 20 '13 at 11:55

15

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)

answered Oct 20 '13 at 11:55

Atiq

490
11
28

score 11 · Answer 5 · edited Mar 21 '21 at 07:08

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.

edited Mar 21 '21 at 07:08

Glorfindel

21,988
13
81
109

answered Jun 15 '10 at 03:56

Dean Harding

71,468
13
145
180

The nth Catalan number formula `(2n)! / (n+1)!n!` grows exponentially. How do we write an algorithm to solve this for `n > 11` ? – GigaWatts Apr 23 '21 at 15:01

score 7 · Answer 6 · edited Oct 13 '11 at 21:09

7

Different binary trees with n nodes:

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

where C=combination eg.

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

edited Oct 13 '11 at 21:09

sjngm

12,423
14
84
114

answered Oct 13 '11 at 12:28

Sarang

71
1
1

score 5 · Answer 7 · edited Nov 24 '11 at 05:44

5

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

edited Nov 24 '11 at 05:44

Mateen Ulhaq

24,552
19
101
135

answered Nov 24 '10 at 15:49

karthik

59
1
1

score 2 · Answer 8 · answered Apr 28 '21 at 10:01

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.

score 1 · Answer 9 · answered Jul 07 '12 at 13:44

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

score 1 · Answer 10 · edited Aug 22 '18 at 13:17

1

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

edited Aug 22 '18 at 13:17

Michael Dodd

10,102
12
51
64

answered Aug 22 '18 at 13:02

Turing101

347
3
15

Can you explain the 2nCn and (n+1) in the first formula? – Bill Chen Nov 21 '21 at 05:33

score 0 · Answer 11 · answered Aug 18 '14 at 17:45

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

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

11 Answers11

Linked

Related