Design and give the pseudocode for an O(log n) algorithm that determines whether a red-black tree with n keys stores any keys within a certain (closed) interval. That is, the input to the algorithm is a red-black tree T and two keys, l and r, where l r. If T has at least one key k such that l k r, then the algorithm returns true, otherwise it returns false. You cannot use Breadth-First Search Traversal Algorithm. Hint: You can use the TreeSearch algorithm (page 146) as a subroutine. You cannot and PLEASE do use the Breadth-First Search Traversal Algorithm for this one.

Here is treesearch for reference:

Algorithm TreeSearch(k,v): Input: A search key k, and a node v of a binary search tree T Output: A node w of the subtree T(v) of T rooted at v, such that either w is an internal node storing key k or w is the external node where an item with key k would belong if it existed if v is an external node then if kkey (v) then else if kkey(v)) return TreeSearch(k,T.rightChild(v)) Algorithm 3.5: Recursive search in a binary search tree. Algorithm TreeSearch(k,v): Input: A search key k, and a node v of a binary search tree T Output: A node w of the subtree T(v) of T rooted at v, such that either w is an internal node storing key k or w is the external node where an item with key k would belong if it existed if v is an external node then if kkey (v) then else if kkey(v)) return TreeSearch(k,T.rightChild(v)) Algorithm 3.5: Recursive search in a binary search tree