UGC NET CSE | June 2013 | Part 3 | Question: 13

Question

In any n-element heap, the number of nodes of height h is,

• A. less than equal to $\biggl[ \frac{n}{2^h} \biggr]$
• B. greater than $\biggl[ \frac{n}{2^h} \biggl]$
• C. greater than $\biggl[ \frac{n}{2^h+1} \biggr]$
• D. less than equal to $\biggl [ \frac{n}{2^h+1} \biggr]$

Comments

Ans is D

https://www.google.co.in/url?sa=t&source=web&rct=j&url=http://www.iitg.ernet.in/psm/indexing_ma252/y12/LectureNoteMA252Jan23.pdf&ved=0ahUKEwjS_cS3h_LWAhUKRY8KHUlgALAQFgimATAU&usg=AOvVaw0ZRweknnsZH0OUxXLLLM65

Answer 1

Take n= 4 for binary heap...height h should be 2

So (n/2^h ) = gives 1 ... While taking root at 0th height..

Just check placing only  one node at height h..

So ans should be B.

Comments

of height h   i think root is of height h  and leaves are of height 0