One of the answers in our powerpoint says it is n/2 leaves, but I am seeing another answer which says (n+1)/2. I was wondering which one is correct if any, and why?
In the simplest case a binary tree with a root node, a left and a right has 3 nodes, two of which are leaf nodes. It's (n+1)/2.
If your total number nodes are n
, and i
are the total number of internal nodes ,i.e., whose degrees are 1. If the tree considered is a binary tree, then this relation holds true.
2i + 3 = n
. Root and leaf nodes are not internal nodes.
Hence, 2i + 3 = 1 + i + l
where l
is number of leaf nodes.
This gives us, i + 2 = l
. and we know that i = (n-3)/2
. Hence, l = (n+1)/2
. Hope this helps
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With