Option is B.
for every node -all numbers in one subtree are less than all numbers in the other subtree .
Firstly chose a value for root $- 9$ elements = $\mathbf{9}$ ways
Now, we hv $\mathbf{8}$ elements left - we hv to chose $\mathbf{3}$ for left subtree & $\mathbf{5}$ for right subtree.
Note: Here we can either chose $3$ nodes from beginning or end out of 8 elements we have ! $= \mathbf{2}$ ways
Now,we hv $3$ elements for left subtree & $5$ for right(Consider subtrees of subtree).
Left Subtree :
whatever way we place , always one side is smaller than other {$6$ is smaller than $8$ in above example given in question} so, total ways $= \mathbf{3!} $ {three places put one by one} $=\mathbf{6}$ ways
Right Subtree :
Right subtree has two more sub-trees ,so that elements on one side should be smaller than other **
Steps :
- Select one element for root $=\mathbf{5}$ ways
- $4$ elements left ,Select one element for left $=\mathbf{2}$ ways {Either we can chose from left or right}
- $3$ elements left, for right subtree $=\mathbf{3!}$ ways $=\mathbf{6}$ ways
Total ways $= 9*2* 3! * 5 * 2 * 3! = 2^4* 3^2 * 5 * 9 = 6480 =$ B (Ans)