-3
$\begingroup$

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.

Question:

enter image description here

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.

$\endgroup$
  • 1
    $\begingroup$ Don't use images as main content of your post: it makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and maths (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$ – D.W. Jun 15 '14 at 19:32
  • 1
    $\begingroup$ Also, this question is not the place for code or questions about code. I suggest you edit your question to remove the code entirely (or if you must include it, edit out the code and replace it with pseudocode that should be understandable to anyone without knowledge of any specific programming language). $\endgroup$ – D.W. Jun 15 '14 at 19:33
1
$\begingroup$

If $i$ is bounded by a constant, simply search for $k$ and then do BST-successor $i$ times.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.