Let T be an augmented red-black tree, where each node x has an attribute x.size, which is the number of internal nodes in the subtree rooted at x. Given such an augmented red-black tree T, a value low, and a positive integer k, describe an e?cient method for ?nding the k smallest values in the dictionary that are greater than low.
Your method should take much less than O(n) time whenever k is much less than n.
Analyze the time for your method