2.3K
Question: How many binary trees are possible with n nodes?
Input: Nodes = 3
Output: Answer = 5
For, example consider a tree with 3 nodes (n = 3), it will have a maximum combination of 5 different trees
In general, if there are n nodes, there exist (2n)!/(n+1)! different trees.
4 comments
(2n)!/(n+1)! is the answer.
Catalan Number is for BST
no you are wrong the number of possible binary trees with 4 nodes is 14, but 2^4-4 is not 14.
I think total number of binary trees possible for n nodes is equal to Catalan number
C(n) = (2n)! / ((n+1)! * n!)
for n = 4, 14 binary trees are possible as given by catalan number. While 2^n-n = 12. for n=4
http://en.wikipedia.org/wiki/Catalan_number
Hi Amit,
For a binary “search” tree, the possible combinations is C(n), the Catalan number, we are talking about binary trees in general.
Thanks for the extra information though. :)
Comments are closed.