educative.io

The total number of non-leaf nodes in a complete binary tree of height “h”

Courses
,
#1

A reader sent us the following feedback:

"The total number of non-leaf nodes in a complete binary tree of height “h” is expressed as." I am comfused about this range. why h-1?

#2

Hi,

This is Fatimah Abdullah from Educative. Thank you for reaching out to us!

In response to your feedback, the reason we have used h instead of h-1 is that we have determined that the height of the leaf node is 0 instead of 1. Some authors might define it from 1. As long as we stick to one convention it does not really matter which convention is being used. Let’s do a dry run for two trees with height = 3.

A complete binary tree with the least number of nodes and height = 3 can be the following:

       1            
      / \        
     0   2        
    / \ / \
   3  5 1  4      
  /
 6                

h = 3
least number of non-leaf nodes = 2^(h - 1) 
                               = 2^(3 - 1)
                               = 4

A complete binary tree with the maximum number of nodes and height = 3 can be the following:

         1            
      /     \        
     0      2        
    / \     / \
   3   5   1   4      
  / \ / \ / \ / \
 6  1 3 4 5 1 9  2     

h = 3
max number of non-leaf nodes = 2^(h) - 1   
                             = 2^(3) - 1
                             = 7

I hope this clears up your confusion.

Thank you for reaching out to us! If you have any further queries or concerns, please let us know.

Best Regards,
Fatimah Abdullah | Developer Advocate
Educative

1 Like