Q:

Minimum finger search tree complexity

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?  

A:

Yes, you might be looking it the wrong way. 

If $x$ is larger than the tree's root's key (the median, or equivalently $k>n/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)$.

First, let us be accurate.  The root's key may not be the median, although it sits roughly in the middle. 
Let $r$ be the root node.  Let $n$ be the number of nodes in the whole tree and $n_l$ be the number of nodes in the left subtree of $r$. Let $h_l$ be the height of that subtree and $h$ be the height of the tree, so $h\le h_l+2$ since an AVL tree is height balanced.  
Suppose $x$ is larger than the root's key.   That means
$$n_l < k \le n.$$ We also have, according to the properties of an AVL tree. 
$$\log_2 (n+1)\le h \le h_l+2 \le c\log_2(n_l+2)+b +2\lt c\log_2(k+2)+b +2$$ 
where $c\approx 1.44$, $b\approx -0.328$. So, for all $k\ge3$,
$$\log_2(n)\le2\log_2(k)$$
So if you have traversed the entire (height) of the left branch in order find the $k$-th smallest element, you will use $O(\log n) = O(\log k)$ steps. 
In fact, if we only look at the subtree whose root is the highest node that we will climb to in search of the $k$-th smallest element, we have just proved that the worst case complexity is always $O(\log k)$

