In the following three questions, use the following definition of the tree datatype.

  datatype tree = Leaf of int | Node of tree * tree

1. [Points 2] Say what is the meaning of the following function. Choose only one answer.

   fun g (Leaf n) = [n]
     | g (Node(left,right)) = (g left) @ (g right);
   

   1. g takes a tree t and returns the maximum element of t
   2. g takes a tree t and produces the list of integers according to the left-to-right traversal of t
   3. error, because @ is an operator on lists
   4. g takes two trees and produces a new tree containing them as subtrees.


2. [Points 3] Consider the following function.

   fun pick (Leaf N) = N
     | pick (Node(left,right)) = 
         let val (x,y) = (pick left, pick right)
          in if x < y then x else y
         end;
   

   What function does pick compute? Pick only one answer.
   1. pick returns the minimum integer for all integers labels in the input tree.
   2. pick returns the maximum integer for all integers labels in the input tree.
   3. error, because a pair of pick values is used.
   4. pick always returns the left-most label in the input tree.


3. [Points 5] Consider the function below.

   fun sumup (Leaf n) = n
     | sumup (Node(left, right)) = (sumup left) + (sumup right);
   

   This function will sum up all the integers labeling leaves in the input tree.
   Write a new function, called opup similar to this function except that it has type

   (int * int -> int) * tree -> int

   and where the first argument to opup is to be used instead of the plus (+).
   For example, if T denotes a tree, then the expressions (sumup T) and (opup (op +, T) should always be the same value, and where opup(op *, T) returns the product of the numbers labeling leaves, and where opup(max, T) picks the largest integer labeling leaves (where max is a function from a pair of integers to the maximum of those integers).

fun opup (Op, (Leaf n)) = n
  | opup (Op, (Node(left, right))) = Op(opup(Op, left), opup (Op, right));