retagged by
22,301 views
81 votes
81 votes

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 

  1. $n-k+1$
  2. $n-k$
  3. $n-k-1$
  4. $n-k-2$
retagged by

6 Answers

Best answer
77 votes
77 votes

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.

https://gatecse.in/number-of-binary-trees-possible-with-n-nodes/

edited by
3 votes
3 votes

Total number of nodes (n) = left subtree nodes + right subtree nodes(i.e x in the question) + 1(i.e for root)

                                       n = (k-1) + x + 1    respectively 

                                       x = n-k 

edited by
Answer:

Related questions

25 votes
25 votes
3 answers
2
Kathleen asked Sep 16, 2014
23,358 views
Suppose the numbers $7, 5, 1, 8, 3, 6, 0, 9, 4, 2$ are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering o...