Home Theory How many binary trees are possible with n nodes?

How many binary trees are possible with n nodes?

by nikoo28
4 comments

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

different_trees
In general, if there are n nodes, there exist (2n)!/(n+1)! different trees.

4 comments

You may also like

4 comments

Abhishek Malviya July 26, 2017 - 17:44

(2n)!/(n+1)! is the answer.
Catalan Number is for BST

Reply
chris April 28, 2017 - 01:22

no you are wrong the number of possible binary trees with 4 nodes is 14, but 2^4-4 is not 14.

Reply
Amit March 14, 2015 - 19:17

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

Reply
nikoo28 March 16, 2015 - 00:48

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

Reply

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More