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

Option Verification Technique
We know that T(0) = 1 {Empty tree is valid BST}
T(1) = 1
T(2) = 2 
and we can verify options using K = 3 
You'll find it right 

---

We can use catalan no. concept  for number of BST from n nodes C(2n,n) / (n+1)

---

• Root Choice: Pick the \(k\)-th element out of \(n\) elements as the root of the tree.

• Left Subtree: Contains the elements smaller than the root, which are \(k-1\) elements, giving \(T(k-1)\) possibilities.

• Right Subtree: Contains the elements larger than the root, which are \(n - k\) elements, giving \(T(n-k)\) possibilities.

• Total Count: Multiplying the independent choices for both subtrees and summing over all possible choices of root \(k\) from \(1\) to \(n\) yields \(T(n) = \sum_{k=1}^{n} T(k-1)T(n-k)\)

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

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​

---

@Arjun sir, link is showing database error

Answer 2

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

Comments

simple and sweet

---

best answer 🏆

---

But how did you get that idea . I mean is there any proof

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.

Answer 5

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

Ashutosh777

so number of BSTs possible with zero nodes = 1?

---

An empty tree is also considered as a binary search tree.
So with 0 nodes we will have 1 BST, thus T(0) = 1.
 

---

An Empty Tree is a BST

A Binary Search Tree (BST) is defined by a strict rule: for any given node, all nodes in its left subtree must have smaller values, and all nodes in its right subtree must have larger values.

Because an empty tree has no nodes at all, it is impossible for it to violate this rule. In discrete mathematics, this is known as a vacuous truth. Since no rule is broken, an empty tree is universally accepted as a valid BST.

In the world of computer science and data structures, T(0) = 1 is the universal baseline for almost any rooted tree.

 

Answer 6

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)