GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
220 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 ________

asked in DS by Boss (8.8k points)   | 220 views

2 Answers

0 votes

Suppose consider 15 elements 1,2,3,4,....15.

It is min heap ,level by level elements are stored.Root is at 1st level.

1st level; 1

2nd level: 2,3

3rd level: 4,5,6,7

4th level: 8,9,10,11,12,13,14,15.

In the second level elements are nodes 2,3 occupies 2 ways.no matter because it satisfies the heap property.

In the 3rd level also same nodes are 4,5,6,7 can be arranged in 4! ways.

In the 4th level 8!

SO TOTAL NO OF TREES ARE 1!*2!*4!*8*=1935360

answered by Veteran (11.1k points)  
What about a heap like this:

1st level: 1

2nd level: 2 5

3rd level: 3 4 6 7

4th level: 8 9 10 11 12 13 14 15

This is also valid according to the question but the answer does not account for these type of heaps.
i miss it,but this type of problems construct every min heap tree construction is so difficult.

so i think nearest no of min neaps consideration is better.
0 votes
Ans should be 8!*7! max 8 values will be tere in leaf, there are 8 nodes they can be arrange in any way and 7 in non leaf they can be arrange in any way.
answered by Junior (821 points)  

Related questions

0 votes
0 answers
2
asked in Algorithms by vivek9837 Junior (921 points)   | 35 views
+1 vote
0 answers
3
asked in Programming by S Ram Active (2.4k points)   | 156 views


Top Users Sep 2017
  1. Habibkhan

    8796 Points

  2. rishu_darkshadow

    3566 Points

  3. Warrior

    2914 Points

  4. Arjun

    2840 Points

  5. A_i_$_h

    2550 Points

  6. manu00x

    2268 Points

  7. nikunj

    1990 Points

  8. Bikram

    1874 Points

  9. makhdoom ghaya

    1820 Points

  10. SiddharthMahapatra

    1718 Points


26,346 questions
33,926 answers
80,524 comments
31,232 users