+32 votes
2.4k views

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

1. $n-k+1$
2. $n-k$
3. $n-k-1$
4. $n-k-2$
asked in DS
retagged | 2.4k views

## 3 Answers

+32 votes
Best answer

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.

http://gatecse.in/wiki/Number_of_Binary_trees_possible_with_n_nodes

answered by Veteran (346k points)
edited by

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

watch this video for clarity.

+33 votes
left subtree + root + right subtree = total node
(k-1) + 1 + x = n
x = n - k
answered by Veteran (53.4k points)
+28 votes

Option B

answered by Veteran (26.9k points)
edited
Thank U very Much !!! I got this Knot !!!
thank u sir .....
Answer:

+20 votes
4 answers
1
+14 votes
1 answer
2
+20 votes
2 answers
3