Count the binary tree

Computer Science Level 3

How many distinct binary trees can be formed with three unlabeled nodes?

Bonus : Can this be generalized for any n n unlabeled nodes?


The answer is 5.

Beakal Tiliksew by Beakal Tiliksew , 24, Ethiopia

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Bhavesh Gulecha
Jul 17, 2017

Actually is is equal to catalan number (2nCn)/(n+1)

0 Helpful 0 Interesting 0 Brilliant 0 Confused
Vijay Kumar
Jan 19, 2016

It doesn't matter that the nodes are labelled or not. The number of binary trees possible with n nodes is the catalan_number(n). 

def catalan_number(n) :
    return (math.factorial(2*n))/(math.factorial(n)*math.factorial(n+1))
0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...