This might help..

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

- $n-k+1$
- $n-k$
- $n-k-1$
- $n-k-2$

## 5 Answers

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/

### 3 Comments

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.