这只是一个想法的概述：
在BST中，节点的左子树
T仅包含小于中存储的值的元素
T。如果
k小于左侧子树中的元素数，则
k第最小元素必须属于左侧子树。否则，如果
k较大，则
k最小的元素在右子树中。
我们可以扩展BST，使其中的每个节点都在其左侧子树中存储元素数（假设给定节点的左侧子树包括该节点）。有了这些信息，就很容易遍历树，方法是反复询问左子树中的元素数，以决定是否要递归到左子树或右子树中。
现在，假设我们在节点T上：
- 如果 k == num_elements（T的左子树） ，那么我们正在寻找的答案是node中的值
T
。 - 如果 k > num_elements（T的左子树），则显然我们可以忽略左子树，因为这些元素也将小于
k
第th 个小元素。因此，我们将问题简化为找到k - num_elements(left subtree of T)
正确的子树的最小元素。 - 如果 k <num_elements（T的左子树），则第
k
thk
个最小元素在左子树中的某处，因此我们将问题减少到在左子树中找到第th个最小元素。
复杂度分析：
这需要
O(depth of node)时间，这
O(log n)在平衡的BST上最差，
O(log n)对于随机BST则平均。
BST需要
O(n)存储，而另一个则需要
O(n)存储有关元素数量的信息。所有BST操作都需要
O(depth ofnode)时间，并且需要花费
O(depth ofnode)额外的时间来维护“元素数量”信息以用于节点的插入，删除或旋转。因此，在左子树中存储有关元素数量的信息可保持BST的空间和时间复杂性。
