如果简单的利用定义：每调用一次该函数就需要O(h)时间，调用k次就需要O(kh)时间。这种想法是没有深入分析题目中函数具体调用过程。如果明白12.2-7题目核心内容。就知道，除了第一次调用该函数需要O(h)时间外，其余的连续k-1次遍历了连续的k-1个结点，这k-1个结点有k-2个边，而每条边最多遍历2次。所以总时间T=O(h)+2(k-2)=O(h+k).为什么k-1个结点有k-2个边，可以举例一些图像

来解释。

假设我们有一棵二叉搜索树，其中每个节点都表示一个整数。我们想要找到这个树中第k小的元素。我们可以用深度优先搜索来找到这个元素。

首先，在深度优先搜索中，我们需要遍历每个节点。对于这个二叉搜索树而言，如果我们从根节点出发，我们将首先遍历它的左子节点，然后是它的右子节点。

当我们到达某个节点时，我们需要计算它的排名。如果节点左子树中有n个节点，则该节点的排名为n+1。如果n恰好等于k-1，则该节点就是树中的第k小元素。否则，如果n>k-1，则我们可以继续在该节点的左子树中查找第k小的元素；如果n<k-1，则我们可以在该节点的右子树中查找第k小的元素，其中k减去n+1。

在上述过程中，我们发现每个节点至多被访问两次：一次是在从根节点到该节点的途中，另一次是在从该节点返回其父节点的途中。因此，最糟情况下，我们将遍历k-1个节点（排名小于等于k-1）和k-2条边（节点之间的边）。因此，总时间复杂度为O(hk)，其中h是树的高度。

下面是一个例子（以红黑树为例）。假设我们想要查找红黑树中排名为3的元素。我们首先从根节点出发，遍历到5，发现5的排名为1+1=2，继续遍历其右子树，至节点8，发现8的排名为2+1=3，因此8就是我们要找的元素。在这个过程中，我们遍历了4个节点（5、8、7、6）和3条边，时间复杂度为O(hk)。