Minimum finger search tree complexity
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&gt;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 &lt; 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)$