Starting at the root of the tree, recursively search the left and right subtrees if the root of the subtree has a key value less than $x$. This algorithm takes $O(k)$ time, because there is no node in $T$ storing a key larger than $x$ that has a descendent storing a key less than $x$.