Suppose that a maxheap has height 10 and stores only unique

Suppose that a max-heap has height 10 and stores only unique keys. At which levels of the heap can the 4th smallest key be stored?

Solution

Suppose that we have k nodes in our heap and n be the 4th smallest element in the heap which means that all the decendents of node n have larger keys .so, the maximul number of decendents are three.The leaves in the heap have no elements and at level h. nodes at level h-1 can have elements say 9 (in our case) and h-2 can have 8 .So, the fourth smallest element can be of h,h-1,h-2 levels.