Consider the following proposed extension to an AVLTree class. T is any type. We’d like to add a method T firstAfter(T v) that, given a value v, returns the least element of the set that is ≥ v. If no such element exists, the method should return a special value “notFound”. v itself may or may not be in the set.

1. Suppose we implement firstAfter() as a top-down tree walk. What should we do if the root of the tree has a key < v? Justify why the behavior you specify is correct.

2. If the root has a key k > v, what should we do to determine whether k is the least key ≥ v? Justify why the behavior you specify is correct.

3. Based on your answers above, give pseudocode for an implementation of firstAfter() that runs on a BST in time proportional to its height.