max heap - algorithms - made easy test series

Question

Consider the following graph:

Find the total number of max-heap possible orderings with elements 12, 10, 1, 5, 7, 9, 8 such that each element is filled in one node of the above tree and element 10 occupies only the left child node of its parent.

Comments

firstly, I stopped reading the question at “...max-heap possible orderings with elements...” because the given graph isn’t a full binary tree. Hence, no ordering of the given elements will be a max-heap. So the answer should be 0 according to me.

secondly, the answer given is 20 and I don’t quite understand what the question is asking for. Have I misinterpreted the question? 

---

Assuming they have just given the wrong diagram.
The answer should be 40.

If the above-given graph is indeed a heap, allocating 10 to root’s ie 12’s left child, we will have 3 “linear”, spaces on RHS and 2 spaces on LHS with 5 remaining vertices. Selecting 3 vertices from 5 for RHS, and due to being linearly ordered, which can be only done in 1 * 5C3 ways, the remaining 2 can be allocated in 2 ways, with a total of 2* 5C3 = 20.

> Have I misinterpreted the question?
Possibly, but in the real GATE exam, I am sure it will be mentioned clearly what the “problem’s” definition of a heap is.

---

The (binary) heap data structure is an array object that we can view as a nearly complete binary tree (see Section B.5.3), as shown in Figure 6.1. Each node of the tree corresponds to an element of the array. The tree is completely filled on all levels except possibly the lowest, which is filled from the left up to a point. –Definition of Heap from Coremen

Considering this, the given tree structure is not at all a heap . I don’t understand why they frame questions so poorly .

 

Answer 1

Except this we don’t have any other option to put 12 and 10 with fo

Now for childs of 10 we have   $\binom{5}{2}$ option and we can arrange them in $2!$ ways. Total=$\binom{5}{2}$*$2!$=20

Now on right side we don’t have any option because of left screw stree.

So Answer=20.