-3

if T(n) is the number of different binary search trees on n distinct elements then

The recurrence relation
(source: imgsafe.org)

what is the value for x please explain.

Glorfindel
  • 21,988
  • 13
  • 81
  • 109
coder
  • 41
  • 1
  • 8
  • @Sneftel its about recurrence relation used to find the time complexity of the algorithms so why its off topic please explain – coder Dec 28 '15 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 https://stackoverflow.com/a/12531995/4687565 – Dimitry Oct 02 '19 at 07:39

1 Answers1

1

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.

Karoly Horvath
  • 94,607
  • 11
  • 117
  • 176
  • 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 – coder Dec 28 '15 at 12:33