Consider element 12,10,8 and given B-tree. Find no. of possible max-heap possible.
We have to find no. of possible max heap in this tree.We know that arrangements are 10,12,8 and 8,12,10 Mathematically, it should have been 3!, but what we are doing is we are fixing 12 at position 2nd of array.
∴ We have to divide it by 3 to reduce what we earlier have multiplied to each element as we have now fixed one of them.
∴ no. of total possible arrangement after fixing = 3!/3 = 2
Again we will take 4 elements 10, 3, 4, 8 and a B-tree Find no. of max-heap possible.
sol : We will our intuition and logic as this problem is problem is small to draw all possible b-tree to be able to fill our max-heap requirements.
So, given is our three required Max-heap. Mathematically, we will try. For 4 element total arrangement is 4!
Now, in max-heap at any subtree root must have highest of all it’s node. So first we will fix largest of all element i.e. ‘10’ to top. Which make us divide by 4 to earlier 4! as element 10 must have multiplied to give 4! arrangements. But note 10 is fixing at a particular position in normal array it is position 3 which lead to 2 subarray. One having 2 element and second having 1 element. Now again we have 2 seat to left of element 10. Position 2 seat i.e. just left of root (10) will again occupy the bigger among two. So again we have to divide by 2 to above 4!. Now we are left with 2 subtree with each 1 element.
So. Total possible max-heap in this arrangement = 4!/4.2.1.1 = 3
So, Concept is in this type of question that first take n! then divide by n and then keep dividing by no. of nodes in subtree of each node starting from root.
So coming back to our question we will get :
∴ Possible no. of Max-Heap possible = 9! / 9.5.3.3 = 896