475 views
The number of ways , in which numbers 1,2,3,4,5 can be inserted into binary heap,such that resultant binary heap is max heap ?

given ans :8
should'nt it be 4??
given is 8 , m getting 9

Yes, It is 8. [ Thanks @Kapil , @Sonam :) ]

1. 5, 4, 3, 2, 1

2. 5, 4, 3, 1, 2

3. 5, 3, 4, 2, 1

4. 5, 3, 4, 1, 2

5. 5, 4, 1, 2, 3

6. 5, 4, 1, 3, 2

7. 5, 4, 2, 3, 1

8. 5, 4, 2, 1, 3.
selected by
when 4 is 2nd node then 1,2,3 any can be any leaf right ..you missed that cases rt
@vijaycs SIR is there any mathematical approch for the same question ? Like say if n nodes are to be inserted

@vijay

what if an array of 100 elements given?
cant always go with hit n trail...there should be a generalised way keeping in mind height factor and how many will be in left subtree and how many in right
Ans 8,rt?

how [email protected]

@sudsho

Yes, what if 100 elements ?

This shows some generalization but I have never applied it. Should we try ?

i did with permutation which you considered but writing all cases ,..  but it will take time and if you miss any case then it will give wrong ans ,

i did like first fix 5 as root( 1 way) then , at 2nd level 3,4 node so there 2 cases

1) when 3 is 2nd node then 3rd node fixed 4 and other 2 nodes either 1,2 (2 ways)

2) when 4 is 2nd node then remainning nodes will pe arrange in 3! way = 6 ways

so total 6+2+1 =9 , yes ans is 8 but where i am leaking ?
yes , given soln is same in test series.
5 fixed not a case here.

until we go upto leaf , we cannot consider a way.
Ok... :) Keep in mind

This is through Brute Force... Is there any formula?

Answer wil be 8 only . First th will be fixed to the root .

Now it is difficult to see from the internal nodes see from leaves. The remaining elements are (1,2,3,4). There will be 2 leaves possible. So possible pairs will be .

if we choose (1,2) in leafs then the possiblity for its root is (3 or 4) . So 2 choices for root and 1,2 can also be arranged in 2 ways - total choices = 2*2 = 4
like wise

(1,3) - 1 choice i.e 4. but arrangement of 1,3 or 3,1 possible - 2*1 choices - 2

(1,4 ) not possible

(2,3) - 1 choice = 1*2 = 2 choices

(2,4) not possible

(3,4) not possible

total ways = 4+2+2 = 8 choices
Thanks

1
2