if T(n) is the number of different binary search trees on n distinct elements then
(source: imgsafe.org)
what is the value for x please explain.
- @Sneftel its about recurrence relation used to find the time complexity of the algorithms so why its off topic please explaincoder– coder2015-12-28 11:51:47 +00:00Commented Dec 28, 2015 at 11:51
- I don't know why would someone bring back the question form four years ago, but just in case anyone bothers, the answer was given seven years ago stackoverflow.com/a/12531995/4687565Dimitry– Dimitry2019-10-02 07:39:53 +00:00Commented Oct 2, 2019 at 7:39
Add a comment |
1 Answer
Any element can be the root of the tree. The rest of the elements will go in the left or right sub-tree depending on whether they are smaller or larger than that element.
Those sub-trees are also binary search trees, so based on this you can write a recurrence relation.
The rest is left as an execercise, as this is clearly homework.
1 Comment
coder
Karoly Horvath its not a homework problem it is a question that came in a competitive exam in India since i could not find the solution any where i asked it here