For a complete binary tree with n nodes, how many nodes are leaf nodes?

Question

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?

Newfeld

Answer 1

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.

Abdicate

Answer 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

Ferraro

Answer 3

If someone is saying that n/2 is wrong then (n+1)/2 should also be wrong. When the numerator is an odd number you wouldn't get a natural number, therefore you have to consider the floor or ceil value. So, If you are going to take it as (n/2) then you should ceil it, If you are going to take it as (n+1)/2 then you should floor it.

Exhibit

Since the question explicitly mentions a complete binary tree, n is always an odd number. Therefore (n+1)/2 does not need ceil or floor. – Bonaparte

Number of nodes in a complete binary tree is not always odd. Just take an example, root node with key 'A' and left and right node have key 'B' and 'C' respectively. Then left child node ('B') has a left node with a key value of 'D'. This is a complete binary tree but number of nodes are 4, that isn't a odd number. Number of nodes in Full binary tree is odd but number of nodes in a complete binary tree may vary. – Exhibit