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

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

1. [Points 3] Consider the following function.

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

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


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

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

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


3. [Points 5] Consider the function below.

   fun multup (Leaf n) = n
     | multup (Node(left, right)) = (multup left) * (multup 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 times (*). For example, if T denotes a tree, then the expressions (multup T) and (opup (op *, T) should always be the same value, and where opup(op +, T) returns the sum 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));