Reputation: 13
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
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