Given the following pseudocode, answer the questions:

function xyz(node T, key low, key high): boolean if T = NULL then return TRUE else if (low < key(T)) AND (key(T) < high) then return xyz(left(T), low, high) AND xyz(right(T), low, high) else return FALSE

(a) The function foo can be called on any binary tree T (not just binary search trees). When does it return TRUE and when FALSE?

(b) What is the asymptotic worst-case running time of foo when called on a tree with n nodes? Briefly explain your answer.

(c) Modify this function to write function searchTree. The input to searchTree is any binary tree. The output is TRUE if and only if the binary tree is also a binary search tree. (May wish to assume the existence of constants minKey and maxKey, which are, respectively, smaller and larger than any key that may appear in the tree.)

function searchTree(node T, key low, key high): boolean if T = NULL then