in DS retagged by
62 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$
in DS retagged by


This question is not in GO pdf please include it also.
edited by

$T(n) = \sum_{k=1}^{n} T(k-1)T(x)$

$T(0)\times T(n-1)|$   $T(1)\times T(n-2)|$   $T(2)\times T(n-3)|$ . . . . . . . . . .$T(n-1)\times T(0)$


The binary search tree is almost equal to the Binary tree, so no. of possible BST can be derived from no. of possible unlabeled tree(Every unlabeled Binary tree could be represented as Binary search tee by labelling each node in a way such that it follows binary search tree rule).

This might help


5 Answers

58 votes
Best answer

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.

edited by


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

Sir , how to know that T(k-1)T(x) representing the left subtree and right subtree actually i am not able to understand the question properly , in question it is said that T(n) be the number of different binary search tree so should i check it by options?
That part is to be covered in "recurrence" portion of Discrete Mathematics where one learns to form recurrence relations. I'll upload its slides soon in GO Classroom.
103 votes
left subtree + root + right subtree = total node
(k-1) + 1 + x = n
x = n - k

1 comment

simple and sweet
3 votes

The answer should (a) n-k+1

Try to Solve T(n)=∑ T(k−1)T(n-k+1): 

T(0) = 0 (no of BST with zero node)

T(1) = 1 (no of BST with one nodes)

T(2) = 2   (no of BST with two nodes)

T(3) = 5  (no of BST with three nodes)

T(4) = 14 (no of BST with four nodes)


now verify using both options (a) and (b)

Option(a) : T(n)=∑ T(k−1)T(n-k+1)

T(4) = T(0)T(4) + T(1)T(3) + T(2)T(2) + T(3)T(1)

        =  0 + 5 + 4 + 5

        = 14

which is correct.


now trying the option that is mentioned everywhere 

option (b) T(n)=∑ T(k−1)T(n-k):

 T(4) = T(0)T(3) + T(1)T(2) + T(2)T(1) + T(3)T(0)

         = 0 + 2 + 2 + 0

          = 4

which is wrong as no. of BST which 4 distinct keys = 14

So option (a) should be the answer.




It is not working for n=5 ......
bro T(0) will be 1 as its an empty tree. so if you try it then by putting options you will get option B as the correct answer
T(3) =  5 and T(0) = 1 not 0
2 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


i am not getting the correct answer by putting values, i am getting 3 for T(3), but I should get 5
Then just see the above video u ll definitely get it.
Yes i am also not getting the correct answer. None of the options are matching by putting the values.
2 votes

As easy as that

Option B


Related questions