10,643 views

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$

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

$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)$

$T(x)=T(n-k)$

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

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/

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.
left subtree + root + right subtree = total node
(k-1) + 1 + x = n
x = n - k

1 comment

simple and sweet

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

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

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.

As easy as that

Option B

by