Suppose I have an AVL tree with a pointer to the minimal element. I'd like to conduct a search for some key x, which is the $k$-smallest key in the entire tree. I can do this by "climbing" up the tree's left branch, comparing x with the current key. As long as
(x > curr.key) && (x > curr.parent.key)
I keep climbing up, but once the second condition is violated, I slide down to the current right-subtree, and from there on it's just a standard BST search.
The claim is that the worst case complexity is always $O(\log k)$, for any $k$. But I can't convince myself this is accurate: if x is larger than the tree's root's key (the median, or equivalently $k > {n\over 2}$), that implies I must have traversed the entire left branch, which for a balanced tree is $O(\log n)$ - and only then I can find x in depth of $O(\log k)$.
Am I looking at this the wrong way?