Assume that an ordered dictionary is implemented using a binary search tree, and each node v in the tree has the eld v.size. For this problem you goal is to design an algorithm for ndAllElements(k) and countAllElements(k). The rst method should return a container that has all the elements in the dictionary with key equal to k; the second method should return the number of elements in the dictionary with key equal to k. Now the two methods are very similar but your algorithm for ndAllElements(k) should run in O(h + s) time where h is the height of the tree and s is the size of the output while countAllElements(k) should just run in O(h) time.

So why O(h+s) time for ndAllElements(k)? This running time may look odd; if you think about it though not only should the running time for ndAllElements(k) depend on the height of the tree but also on how many items are in the output. If the output is large say its all the items then the dominant term in h + s is s. But if the output is small, then the dominant term in h + s is h. But 1 because we dont know in advance what the output will be, the running time is expressed as O(h + s).

But why O(h) time and not O(h+s) time for countAllElements(k)? Basically in ndAllElements(k), you have to at least visit every node that contains an item with key k. These visitations account for the s part in O(h + s) part. For countAllElements(k), however, it is possible to design an algorithm so that the number of nodes that contains an item with key k you visit is just O(h) i.e., you may not have to visit all such nodes. To do this, take advantage of the size elds.