2. Finding all vs. counting all. Assume that an ordered dictionary is implemented using a binary search tree and, for each node v in the tree, the field 1. size equal to the num ber of items in the subtree of v is known. Let findAllElements(k) be a method that returns a container that has all the elements in the dictionary whose keys equal k. Let countAllElements(k) be a method that returns the number of elements in the dictio- nary whose keys equal k. For example, suppose the dictionary contains items of the form (birthday, person) and there are ten people in the dictionary whose birthday is March 1. Then findAllElements(March 1) will return a list of these ten people while countAllElements(March 1) will simply return 10. Design an algorithm for findAllElements(k) and countAllElements(k). The two methods are indeed very similar but your algorithm for findAllElements(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 findAllElements(k)? This running time may look odd; if you think about it though not only should the running time for findAllElements(k) depend on the height of the tree but also on the number of items in the output. If the output is large say it's 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 because we don't 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)? For the method findAllElements(k), at the very least you have to visit every item whose key equals k. These visitations account for the s part in O(h+s) running time. For countAllElements(k), however, it is possible to visit just 0(h) nodes ( i.e., you may not have to visit all items with keys equal to k!). To do this, take into account the properties of the binary search tree and the size fields of the nodes. 2. Finding all vs. counting all. Assume that an ordered dictionary is implemented using a binary search tree and, for each node v in the tree, the field 1. size equal to the num ber of items in the subtree of v is known. Let findAllElements(k) be a method that returns a container that has all the elements in the dictionary whose keys equal k. Let countAllElements(k) be a method that returns the number of elements in the dictio- nary whose keys equal k. For example, suppose the dictionary contains items of the form (birthday, person) and there are ten people in the dictionary whose birthday is March 1. Then findAllElements(March 1) will return a list of these ten people while countAllElements(March 1) will simply return 10. Design an algorithm for findAllElements(k) and countAllElements(k). The two methods are indeed very similar but your algorithm for findAllElements(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 findAllElements(k)? This running time may look odd; if you think about it though not only should the running time for findAllElements(k) depend on the height of the tree but also on the number of items in the output. If the output is large say it's 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 because we don't 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)? For the method findAllElements(k), at the very least you have to visit every item whose key equals k. These visitations account for the s part in O(h+s) running time. For countAllElements(k), however, it is possible to visit just 0(h) nodes ( i.e., you may not have to visit all items with keys equal to k!). To do this, take into account the properties of the binary search tree and the size fields of the nodes