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 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.

 

   

Comments

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

---

Ashutosh777

so number of BSTs possible with zero nodes = 1?

Answer 2

No. of the element in left subtree is k-1 

^{“-1” denote that root is not included as leftsub tree
if n is total no. of elements and no.of elements in left subtree is k-1}

No. of  element in right subtree is 
total no. of element – no. element in left subtree – 1(excluding root)



n-(k-1)-1 =  n-k     (Ans)