NIELIT 2021 Dec Scientist A - Section B: 61

Question

Let $\text{T(n)}$ be the number of different binary search trees on $\text{n}$ distinct elements-then $\text{T(n)} = \displaystyle{\sum_{k=1}^{n}} \text{T(K-1)} \; T(x)$ where $x$ is:

• A. $\text{ n – k + 1}$
• B. $\text{ n – k}$
• C. $\text{ n – k – 1}$
• D. $\text{ n – k – 2}$

Comments

Answer for this should be B

Answer 1

BST(N) = $\; \sum_{0}^{n-1}$BST(L) .BST(R) ; where L is node in left subtree and R is node in right Subtree. And L+R = N-1;

using this above equation x = n-1-k+1 = n-k;

so answer of this question is B) n-k