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
Incorrect logic.

8! Won't even come there.

Leaf will always contain max elements.

 

8! Logic is incorrect
0

Why do you think so?

We have 8 leaf node, which we can fill with $[8,15]$

o     o      o     o      o    o      o     o

8      9     10    11   12   13    14    15

8      9     10    11   12   13    15    14

8      9     10    11   12   14    13    15

...

All 8! permutations of $[8,15]$ will be valid. Hence you have 8! ways to fill the bottommost level. So, 8! should definitely come there.

0
because, it is a min heap, and also a full binary tree at the same time.

A full binary tree which is a min heap, always have maximum elements in the last level

so the answer is not what you calculated.
0

 always have maximum elements in the last level

What do you exactly what to say?

See, if we consider $[1,15]$ as the elements, then $[8,15]$ will be the maximum elements, right?

Now, we have to place these elements in the leaf nodes. So, assume the nodes as containers and maximum elements as items, now how many ways do you have to place $8$ items in $8$ containers? Of course $8!.$ 

 

Also, I didn’t get the meaning of this:

A full binary tree which is a min heap, always have maximum elements in the last level

Consider a heap with $7$ nodes, this will be a full binary tree too. If the elements are $[1,7]$, then the maximum $4$ elements will be {4,5,6,7}, but the following min heap is still valid without considering all of these elements in the leaf nodes:

 

              1

         /         \

     2               5

  /    \            /    \

4      3         7      6

 

In a Min Binary Heap, the key at root must be minimum among all keys present in Binary Heap. The same property must be recursively true for all nodes in Binary Tree. (Reference)

  1. 1 is smallest among all keys and it is present in the root.
  2. For the left sub tree, $2$ is minimum among {2,4,3} and it is present in the root of left sub tree.
  3. For the right sub tree, $5$ is minimum among { 5,7,8} and it is present in the root of right sub tree.

 

Notice that $3$ is a leaf node, and $3$ not one of the $4$ largest elements in the range $[1,7]$, and $5$, which is one of the $4$ largest elements is not present in leaf node, still this is a valid min heap, according to the definition of min-heap.

 

We chose $8$ largest elements for this question, because it was explicitly mentioned that the elements in the leaf nodes must be greater than all non-leaf elements. I mean to say that, a full binary tree which is a mean heap will not necessarily have maximum elements in the leaf nodes. We considered this constraint, only because it was explicitly mentioned in the question. Also, we can can change the relative orderings of these elements, hence we will have 8! permutations in which these elements can occur in the 8 leaf nodes.

 

 

0
Why are you considering min heap of 7 elements in the first place

The answer is min heap of 15 elements.

No matter how u draw the tree.

Leaf will always have max elements

Otherwise

Answer should be 2! * 4! * 8! As per your logic which is illogical
0
I considered $7$ element heap only to show that a full binary tree which is a mean heap will not necessarily have maximum elements in the leaf nodes.
0
And, how did $2!*4!$ come in my logic?

 

Do you agree with this part in the answer?

$^6C_3∗2∗2$
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