GATE CSE 2003 | Question: 6

Question

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 

• A. $n-k+1$
• B. $n-k$
• C. $n-k-1$
• D. $n-k-2$

Comments

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

---

This question came in NIELIT STA 2021

Answer 1

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/

Comments

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.

---

We can write this equation also as ?

Cn​=∑i=0 to n−1    ​Ci​⋅Cn−i−1​

Answer 2

left subtree + root + right subtree = total node
(k-1) + 1 + x = n
x = n - k

Comments

simple and sweet

---

best answer 🏆

Answer 3

As easy as that

Option B

Answer 4

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 

Comments

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.