Suppose thatppoints to a node in a complete linked binary tree. It is not a binary search tree! Each nodephas a keyp.key, a pointer to its left subtreep.left, and a pointer to its right subtreep.right. An empty subtree is written as NIL. The procedure IN-TREE returns TRUE if the tree whose root isphas a node with the keykin it. IN-TREE returns FALSE otherwise.

IN-TREE(p,k) ifp== NIL returnFALSE elseifp.key== KEY returnTRUE else returnIN-TREE(p.left,k)orIN-TREE(p.right,k)

Can the master theorem be used to determine the run time of IN-TREE? There are three possible answers.

2. The master theorem canneverbe used. Briefly explain why.
4. The master theorem cansometimesbe used. Briefly explain why. Use the master theorem to determine IN-TREEs run time.
6. The master theorem canalwaysbe used. Briefly explain why. Use the master theorem to determine IN-TREEs run time.

Write your answer in one of these three ways. Hint: ifE is TRUE, thenEorE will not executeE.

3.(10 points.) Suppose thatAis an array whose elements are integers. If you sortAs elements into nonincreasing order, will that turnAinto a max-heap? Prove that it will, or that it will not.