Awesome q2a theme
0 votes
41 views

https://gateoverflow.in/167339/madeeasy-subject-test-programming-%26-ds-heap

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:

                   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 (861 points)
edited by
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
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
13,739 comments
95,564 users