First time here? Checkout the FAQ!
+4 votes
1)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 ________.


2)The number of min heap trees are possible with 15 elements_________________
asked in Programming by Veteran (58.7k points)  
edited by | 358 views

2 Answers

+10 votes
Best answer

1)i am getting 3225600
if numbers are 1,2,3,4...15,
level-1: can be arranged in only one way.
level-2: need to discuss
level-3: need to discuss
level-4: can be arranged in 8! ways. bcoz we need to choose highest 8 elements and rannage them here.
now we are left with 2 subtrees S1 and S2(shown in figure below) 
and 6 elements 2,3,4,5,6,7. 
take any 3 elements and you can arrange these 3 elements in 2 ways in the left subtree, now take the ramaining 3 elements and arrange them in 2 ways in right subtree. (in any 3 elements chosen, one will be the minimum among them, that one element will be the root and remaining two elements can be arranged in 2! ways as children of respective root)
total ways =(6C3*2*3C3*2)*8! = 3225600

this in similar way, root can be arranged in one way
we will be left with 2 subtrees and 14 elements.
choose any 7 elements, minimum among them will be root of left subtree, this root has two subtrees same like previous problem, these two subtrees can be arranged in 6C3*2*3C3*2. so the entire left subtree of the main root can be arranged in 14C7( 6C3*2*3C3*2)
now coming to ryt subtree similar way,
here we choose 7 elements from the remaining. so number of ways of arranging this entire right subtree =7C7( 6C3*2*3C3*2)
total ways=14C7( 6C3*2*3C3*2)*7C7( 6C3*2*3C3*2)

dont know if this is correct. let me know if you find some mistake

answered by Veteran (11.6k points)  
selected by
well explained !!
but in 2)


u r choosing 1 subtree.

Say u choose left subtree.

Now, in 6C3 again u r choosing from left subtree and right subtree (from both)

Which should not be there

sorry,i did not get your doubt
why 6C3 shudnt be there?
14C7- means i chose 7 elements from 14 elements to fill in left subtree. minimum of these 7 elements will be root of left subtree. i need to arrange two children of this left subtree. same like the 1st problem let left subtree be S1 and right subtree be S2. we will have 6 elements as we already arranged 1 elemnt in root. this becomes similar to first problem.
level 1 :1
level 2: 2,5
level3: 3,4,6,7
level-4:  8,9,10,11,12,13,14,15.

is it also maintaining in this solution?
u r fixing root, not selecting root anyway.rt?

then how do u know

level 2: 2,5 orlevel 2: 2,3 ?


Question 2

Question 1

n=15 is a special case where we can solve this like

  • last level nodes = 8 can be permutted in 8!
  • Now the question reduces to The number of min heap trees are possible with 7 nodes

The story will be different when n is  <15 

+1 vote

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 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 (277 points)  
Plz answer 2nd part too I have added
@aman level-2,level3 can also contain 2,5 and  3,4,6,7 respectively.
no Anusha

See this line "every leaf node must be greater than all non-leaf nodes "

i.e why I added 2nd question
yes there are 4 levels.
4th level is leaf nodes level.
but, levels 2,3 are like normal heap ryt?
level 1 :1
level 2: 2,5
level3: 3,4,6,7
level-4:  8,9,10,11,12,13,14,15.
level -4 is greater than all other internal(non-leaf) nodes. this tree satisfies given condition isnt it?

yes, good point

then 1935360+1935360 will be ans.rt?

It doesn't contain because you have to find out heap tree .which alwayz a Complete binary tree or almost complete  binary tree so its not possible
hey, what r u telling??

it is not violating heap property or binary tree property in any way
Actually i am just giving a answer which you have ask above and in question ask every leaf node must be greater than all non-leaf nodes of the tree are that why i have do so and if it is not there same as question 2 they you are right every case possible
plz chk the command again.

U r missed the case what we are discussing.

It should include in answer as well

Related questions

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

Top Users Sep 2017
  1. Habibkhan

    8796 Points

  2. rishu_darkshadow

    3572 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,928 answers
31,231 users