Given Elements : 12,10,8,5,3,2,1,7,9
1) Maximum of all these will be root i.e. Root = 12 ---->1 way --->(1)
2) Remaining : 8 elements
Out of 8 choose 5 for left subtree in 8C5 ways and 3 for right subtree in 3C3 ways. --->(2)
3)Left Subtree :
Out of 5, maximum element is the root.
Out of remaining four , choose 3 for left subtree in 4C3 ways , Out of 3 elements chosen, max is root and rest 2 can be in any of the 2 leaf nodes.
#Heaps possible in Left Subtree= 4C3 * 2 --->(3)
3)Right Subtree :
Out of 3, maximum is root.
Remaining 2 elements can be arranged in 2 leaves in 2 ways.
#Heaps possible in Right Subtree= 2 --->(4)
Hence From (1) to (4) , Total # heaps possible = 1 * ( 8C5 * 4C3 *2 ) * (3C3 * 2 )
=56 * 4 * 2 * 2 =896 (ANS)
