I posted this same question on stackoverflow but I think it might be better suited here as I am having trouble with coming up with an algorithm with O(log(n)) running time.
I am completely lost for this question. I absolutely CANNOT figure out a way to get an algorithm that run in O(log(n)) time. The ONLY algorithm I can think of is to do an in-order traversal, store values in an array and then return the ith smallest key greater than k if it exists but obviously this is worst case O(n). I have been working on this problem for the past 2 days and I simply cannot come up with a solution. The hint my professor gave me was to add a size field to the node which will tell me the number of nodes at subtree v including itself. My thinking was to try to use a relative_rank function (gives me the rank of node value k with respect to a node v) somehow but I cannot think of a way to do it in O(log(n)) time. Any help would be appreciated.