Simple dfs can do the job. We have a counter set to zero. Start from the root and in each iteration check the value of current node; if it is greater than x, then increase the counter and continue the algorithm for one of the child nodes. The algorithm terminates if counter is bigger than equal k or if there is no node left to check. The running time is O(k) because at most k node will be iterated and each iteration is in O(1).
A pseudo-code looks like as follows.
void CheckNode(Node node,int k, int x, ref int counter)
{
if (node.value > x)
{
counter++;
if (counter >= k)
return;
CheckNode(node.Left, k, x, ref counter);
CheckNode(node.Right,k, x, ref counter);
}
}
use it:
counter = 0;
CheckNode(root,index,val,counter );
if (counter >= index)
return true;
return false;
if node.value < x then all children values are smaller than x and there is no need to check.
As @Eric Mickelsen mentioned in comments worst case running time is exactly 2k-1 (k>0) as follows.
The number of nodes visited with values greater than x will be at most
k. Each node visited with value less than x must be a child of a
visited node with value greater than x. However, because every node
visited except the root must have a parent with value greater than x,
the number of nodes of value less than x visited must be at most
((k-1)*2)-(k-1) = k-1, since k-1 of the (k-1)*2 children have values
greater than x. This means that we visit k nodes greater than x and
k-1 less than x, which is 2k-1.