Awesome q2a theme
0 votes

The number of min heap trees are possible with 15 elements such that every leaf node must be greater than all non-leaf nodes of the tree are

in Algorithms by (713 points) | 41 views

1 Answer

+3 votes

Heap with $15$ elements will be a complete binary tree, hence it will have $8$ leaf nodes, and we want all the leaf nodes to be greater than all the non-leaf nodes, hence we can only have largest $8$ elements in leaf nodes. If we place any other elements in leaf nodes then there will be at least one of the largest $8$ elements which we will need to adjust in a non-leaf node, hence given condition will be violated. For example, if the elements are integers from $1$ to $15$ then the elements $[8,15]$ must be present in the leaf nodes, if we place any other element (which will be definitely $<8$) in any leaf node, then one element from $[8,15]$ needs to be adjusted in a non-leaf node, and this adjusted non-leaf node will have element $>$ the element that we placed in the leaf node.


Also, we need the minimum element at the root node,hence the structure of the heap will be:


              /                         \

           x                             x 

       /        \                    /        \

    x             x              x             x

  /   \         /    \         /   \         /   \

o     o      o     o      o    o      o     o


Here denotes a leaf node, denotes a non-leaf node. 

Now, for the $8$ leaf nodes, we can place the $8$ largest elements in any order, and there are $8!$ such orders  …………. (i)


So, we have placed $8$ leaf nodes and the root node, now we are left with $15-8-1=6$ elements.Now, the nodes that we need to fill are represented by in the above heap. From the structure, it is very clear that $3$ of the remaining $6$ elements will be on the left side and remaining $3$ will be on the right side. So, we can select any $3$ of the remaining $6$ elements to be placed in the left sub tree, total ways to do this will be $^6C_3$.  …………...(ii)


Now, for the selected three elements, we need to ensure that the parent element is smaller than both the children, i.e. in the following structure: 


  /    \

b      c

we want to make sure that $a<b$ and $a<c$ to satisfy the property of min-heap, hence, $a$ must be the smallest element among the $3$ elements, and we can also interchange $b$ and $c$ if the above conditions are satisfied, because we know that the leaf nodes are already greater than all the non-leaf nodes. Hence, there are $2$ ways to fill the left part, i.e. we can keep $(b,c)$ or $(c,b)$   ………...(iii)


Similarly, there are $2$ ways to fill right part.  .…….……...(iv)


Hence, total number of ways will be: $8!*^6C_3*2*2=3225600$

by (861 points)
edited by

You are not getting a simple point.

Leaf will always contain maximum.

Suppose you have to make a min heap with 7 nodes.


With 7 nodes maximum elements will be in leaf.

So answer is straightway 6C3 *2*2 for 7 nodes.

But you are without any reason taking internal nodes and calculating minheaps on it. And multiplying it with number of leaf factorial.


I am sure you are still not getting why my point is right.
How can you say this. Show me an example where you have 7 nodes and all maximum elements are not in leaf. Show me

Actually yes, I am not getting your point again. 😅


For an example where you have 7 nodes and all maximum elements are not in leaf, see the 7 node heap that I made in the above comment. where is not in leaf node but is.

Anyways, what is the correct answer according to you then?
21964800 is the answer.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
8,647 questions
2,855 answers
95,564 users