CODEWITHSUNDEEP
algorithmdata-structuresbinary-tree
Surya Teja
Surya Teja

Reputation: 13

What is the no. of distinct binary trees possible with n labeled nodes?

It was given in this link that:

For a binary tree with n nodes, the no. of edges is n−1. So, this problem can be reduced to the no. of ways in which we can make n−1 edges from n vertices. An edge can be made either as a left child of a node or as a right child. Hence, for n nodes, we have 2n possibilities for the first edge, 2n−1 for the second edge and so on. Thus, for n−1 edges, the total no. of ways

= 2n×(2n−1)×(2n−2)×….×(2n–(n–2))

= 2n×(2n−1)×(2n−2)×….×(n+2)

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

I did understand that the first edge can have 2n possibilities because for each node there is left and right child options. I cannot figure out how second edge can have 2n-1 possibilities?

What are the possibilities for second edge when n=3?

Upvotes: 1

Views: 659

Answers (1)

MBo
MBo

Reputation: 80325

how second edge can have 2n-1 possibilities?

There were 2n possibilities until you added the first edge.

After adding the first edge one poiibility is occupied and only 2n-1 possibilities left.

After the second edge only 2n-2 possibilites left and so on

For n=3 there are 6!/4!=30 variants. Just check: there are 5 configurations, every has 6 permutations:

/\    /     /     \     \
     /      \     /      \

Upvotes: 1

Related Questions