The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+43 votes
4.3k 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 by Veteran (52.1k points)
retagged by | 4.3k views
+1
0
This question is not in GO pdf please include it also.

3 Answers

+45 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 (414k points)
edited by
0

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

0
Sir , how to know that T(k-1)T(x) representing the left subtree and right subtree actually i am not able to understand the question properly , in question it is said that T(n) be the number of different binary search tree so should i check it by options?
+2
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.
+59 votes
left subtree + root + right subtree = total node
(k-1) + 1 + x = n
x = n - k
answered by Veteran (59.9k points)
0 votes

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 

answered by Active (1.5k points)
edited by
0
i am not getting the correct answer by putting values, i am getting 3 for T(3), but I should get 5
0
Then just see the above video u ll definitely get it.
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,814 questions
54,518 answers
188,351 comments
75,287 users