Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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?

like image 410
Amit Jain Avatar asked Nov 08 '14 23:11

Amit Jain


2 Answers

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.

like image 59
Robert Bain Avatar answered Oct 17 '22 16:10

Robert Bain


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

like image 44
saruftw Avatar answered Oct 17 '22 16:10

saruftw