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.
This question is related to
tree
binary-tree
catalan
The answer is
Different binary trees with n nodes:
(1/(n+1))*(2nCn)
where C=combination eg.
n=6,
possible binary trees=(1/7)*(12C6)=132
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)
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.
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
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.
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
(2n)!/n!*(n+1)!
The correct answer should be 2nCn/(n+1) for unlabelled nodes and if the nodes are labelled then (2nCn)*n!/(n+1).
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.
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...
Source: Stackoverflow.com