How many leaves are in a given heap and its level

Question

I have a question and it goes like this:

There is a Max heap binary tree.

Let's assume that in the Heap there are (2^2017)-2017 nodes at the bottom-most level.

A)How many levels are there in the heap?

B)What are the number of the Leaves in the heap?

Thanks

Answer 1

A full binary heap that has 2^x nodes at the bottom-most level has (x+1) levels. Consider this heap:

    1
 2     3
4 5   6 7

It has 4 (2²) nodes at the bottom level, and 3 levels.

If the bottom level is full, then the number of leaf nodes is the same as the number of nodes on the bottom level.

In your case, the bottom level has (2²⁰¹⁷)-2017 leaf nodes. We know that the maximum number of nodes possible on this level is 2²⁰¹⁷ (because maximum is always a power of 2). And we also know, from the example above, that there are 2018 levels in the tree.

The number of leaf nodes, however, is not (2²⁰¹⁷)-2017. Consider this heap:

         1
     2       3
   4   5   6   7
  8 9

It has two leaf nodes at the bottom level, and three leaf nodes at the level above the bottom level (5, 6, and 7).

I think you'll find that in your case, the number of leaf nodes is (2²⁰¹⁷)-2017 + 2017/2. The 2017/2 is the number of leaf nodes on the level above.