MAIN75 - BST again
N nodes are labled with integers from 1 to N. Now these N nodes are inserted in a empty binary search tree. But the constraint is that we have to build this tree such that height of tree is exactly equal to H. Your tast is to find how many distict binary search trees exists of these nodes such that their height is exactly equal to H ?
Two BSTs are considered to be different if there exist a node whose parent is different in both trees.
Input First line contains 1<=T<=10 the number of test cases. Follwomg T lines contains 2 integers each. N and H. 1<=N<=500, 0<=H<=500.
For each test case print the required answer modulo 1000000007.
Probably, intended solutions have the complexity of O(n^3), because the difference of the running time between O(n^(2 + epsilon)) solutions and O(n^3) solutions would be almost negligible for small N.Last edit: 2016-12-08 12:58:46
Is the intended solution better than O(N^3)?
VISHAL DEEPAK AWATHARE:
is there a possibilty of like nodes are 3 and height is 20 ? then should we output 0?
Just to clarify again -