Let $T(n)$ be the number of different binary search trees on $n$ distinct elements.
Then $T(n) = \sum_{k=1}^{n} T(k-1)T(x)$, where $x$ is
The summation is for each node, if that node happens to be the root. When a node is root, it will have $(k-1)$ nodes on the left sub tree ($k$ being any number) and correspondingly $(n-k)$ elements on the right sub tree. So, we can write recurrence $T(k-1) * T(n-k) $ for the number of distinct binary search trees, as the numbers on left and right sub trees form BSTs independent of each other and only a difference in one of the sub trees produces a difference in the tree. Hence, answer is B.
Knowing the direct formula can also help in getting the answer but is not recommended.
http://gatecse.in/wiki/Number_of_Binary_trees_possible_with_n_nodes
So, we can write recurrence T(k-1) * T(n-k) for the number of distinct binary search trees, as the numbers on left and right sub trees form BSTs independent of each other.
Please explain this preferably with an example.
@Arjun Sir
watch this video for clarity.
Option B
Gatecse