41 views

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

| 41 views

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:

minimum

/                         \

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:

a

/    \

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 (855 points)
edited
0
No.

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.
0
How can you say this. Show me an example where you have 7 nodes and all maximum elements are not in leaf. Show me
0

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.

0
Anyways, what is the correct answer according to you then?
0