Number of nodes in heap of height 'h'

Question

The number of nodes of height $h$ in any $n$-element heap is ________.

• A. $h$
• B. $2^{h}$
• C. ceil $\left[\frac{n}{2^{h}}\right]$
• D. ceil $\left[\frac{n}{2^{h+1}}\right]$

Answer is given as D, But I think it should be C. Because, even if you take height=1 then possible nodes are 3 and 2. 

Comments

Probably the question was supposed to ask,

The number of nodes of height $h$ in any $n$ element binary heap is at most  ______ 

As in any given heap of $n$ nodes, the lowest level(at height $0$) could be complete or incomplete.

In response to this modified question, D seems the most appropriate answer.

Consider a binary heap of 7 nodes, 

$n = 7$,

It would be a complete binary tree of height $2$.

Number of nodes at height $0$, i.e. at the lowest level  $= 4 = \left \lceil \frac{7}{2^{0+1}} \right \rceil$

Number of nodes at height $1= 2=\left \lceil \frac{7}{2^{1+1}} \right \rceil$,

Number of nodes at height $2$ i.e. at the root level $1=\left \lceil \frac{7}{2^{2+1}} \right \rceil$ 

In the modified question, 

A & B are incorrect,

From Option C it can be inferred that in a binary tree of size $n$ you can have atmost $n$ leaves from $\left \lceil \frac{n}{2^{0}} \right \rceil$, and

from D it can be inferred that in a binary tree of size $n$ you can have atmost $\left \lceil \frac{n}{2} \right \rceil$ leaves from $\left \lceil \frac{n}{2^{0 + 1}} \right \rceil$.

So both of them are correct but D provides a tighter bound than C, so D should be the appropriate choice.

---

P.S. Problem number $6.3-3$ in second and third editions of CLRS asserts this.

---

@Anurag , Can't we consider root to be at height 0 & leaves at height h ?

---

No.

The height of a node in a heap is the number of edges on the longest simple downward path from the node to a leaf.

Also, the height of the heap is defined as the height of its root.

---

the general idea is that there are n nodes in a binary tree, and starting from the root, at each depth there is: 1, 2, 4, 8, 16 ... maximum nodes. We see that at the greatest depth, there is (at most) half of all nodes (n/2). Remember that the height of a node is the distance from the node to a leaf, such that the height of a leaf is 0 (and the height of the root is the height of the tree). So for a leaf, n/2^(0+1) =n/2. For the root, h=log2n, so n/2^(log2n+1)=n/n. And the rest of the tree follows from there.

Answer 1

Answer shd be C.

We can prove it by taking random example.

if we take n=9 and required h=3(e.g.) then according to option d it will produce answer as (9/16=1(ceil))..and thats not correct..

If we consider option C--

(9/8=2) which is correct.

Comments

what if we take n=20 and h=4. then according to option C, we get 2 but the answer will be 5.

I think none of the options is correct.

Correct me if I am wrong.

---

Why it is wrong? At height 3 you have only the root, so you are getting 1.

---

😀 Option D is correct

Answer 2

First, let's observe that the number of leaves in a heap is ⌈n/2⌉. Let's prove it by induction on h.

Base: h=0. The number of leaves is ⌈n/2⌉=⌈n/20+1⌉.

Step: Let's assume it holds for nodes of height h−1. Let's take a tree and remove all it's leaves. We get a new tree with n−⌈n/2⌉=⌊n/2⌋elements. Note that the nodes with height h in the old tree have height h−1 in the new one.

We will calculate the number of such nodes in the new tree. By the inductive assumption we have that T, the number of nodes with height h−1 in the new tree, is:

T=⌈⌊n/2⌋/2h−1+1⌉<⌈(n/2)/2h⌉=⌈n2h+1⌉

As mentioned, this is also the number of nodes with height h in the old tree.

Please upvote if you understand it. :D 

Comments

Source: NPTEL IIT G

Answer 3

Answer should be D

Consider the above Heap where height of each nodes are follows

Height of the node with data 4 is 3

Height of the node with data 2,6 is 1

Height of the node with data 1,3,5,7 is 0

 

Number of nodes present at height 'h' in heap/ Complete binary tree= ceil( n/2^(h+1) ) 

 

In above Heap, find number of nodes at height 1

n=7, h=1

N=ceil(7/2^2)

=ceil(7/4)

=2

node with data 2 and 6 are present at height 1 so it's correct.

Ref: http://www.iitg.ac.in/psm/indexing_ma252/y12/LectureNoteMA252Jan23.pdf

Answer 4

refer these two links: 

https://stackoverflow.com/questions/8814807/find-the-number-of-nodes-of-n-element-heap-of-given-height

https://cs.stackexchange.com/questions/6405/maximum-number-of-nodes-with-height-h