How to find the min and max values of a tree in SML

I have the two datatypes:

datatype 'a Tree = LEAF of 'a | NODE of ('a Tree) * ('a Tree)

and

datatype 'a myTree = myLEAF of 'a | myNODE of 'a * 'a * 'a myTree * 'a myTree

With these two, I need to be able to find the min and max values of a tree.

For example:

findMin (NODE(NODE(LEAF(5),NODE(LEAF(6),LEAF(8))),LEAF(4)))

will produce 4.

I have been working on this for some time now, and I'm quite confused.

Any guidance would be helpful. Thank you.

Solution

You know that there is at least one element in every 'a Tree, so there is always a min/max.

Use pattern matching on each of the two constructors LEAF and NODE, and use recursion in the NODE case, since the two branches might have different min/max values and the min/max for the node is determined by whatever is min/max for its branches. And use the built-in helper functions Int.min and Int.max, if you're finding the min/max integers of a tree. (Your example suggests that this is the case.)

fun findMin (LEAF x) = (* ... *)
  | findMin (NODE (leftTree, rightTree)) =
    let (* ... use findMin recursively on each branch ... *)
    in (* ... find the minimal value of the two branches ... *)
    end

I'm not sure what the 'a myTree type is good for: It is a binary tree in that it has two 'a myTree branches per node, but it also has two 'a elements per node? Should you be interested in finding the min/max of either of those values? Or is one a key and another a value in some tree-based dictionary structure? If so, then why is it 'a -> 'a and not 'a -> 'b? It is hard to solve a problem when you don't understand the problem statement, and the datatype is a large portion of that.

Edit: Since you've provided a solution yourself, let me give some feedback on it:

fun findMin (LEAF(v)) = v
  | findMin (NODE(left, right)) =
      if findMin(left) < findMin(right)
      then findMin(left)
      else findMin(right)

This solution is very inefficient since it calls itself three times for each node's entire subtree. That means the number of function calls roughly follows the recurrence relation f(0) = 1 and f(n) = 3 ⋅ f(n-1). This is equivalent to 3ⁿ or exponentially many calls to find the minimal element in a list of n elements.

Here is a way that take linear time by temporarily storing the result you use twice:
```
fun findMin (LEAF v) = v
  | findMin (NODE (left, right)) =
    let val minLeft = findMin left
        val minRight = findMin right
    in if minLeft < minRight then minLeft else minRight
    end
```
There is no reason to perform the Herculean task of calculating findMin left and findMin right more than once in every node of the tree. Since we refer to it multiple time, a let-in-end is an easy way to bind the results to lexically scoped names, minLeft and minRight.

The expression if minLeft < minRight then minLeft else minRight actually has a name in the standard library: Int.min. So we could do:

fun findMin (LEAF v) = v
  | findMin (NODE (left, right)) =
    let val minLeft = findMin left
        val minRight = findMin right
    in Int.min (minLeft, minRight)
    end

But the reason for using a let-in-end has actually evaporated, since, with the help of a library function, we're now only referring to findMin left (aka minLeft) and findMin right (aka minRight) once now. (Actually, we are referring to them more than once, but that is inside Int.min in which the result has also been bound to a temporary, lexically scoped name.)

So we ditch the let-in-end for a much shorter:
```
fun findMin (LEAF v) = v
  | findMin (NODE (left, right)) = Int.min (findMin left, findMin right)
```
In any case, these are all equally optimal: They use only n recursive function calls for n elements in the tree, which is the least you can do when the elements aren't sorted. Now, if you knew the smaller elements were always to the left, you'd have a binary search tree and you could find the min/max much faster. :-)

Edit (again): Just for fun, you could find the min/max simultaneously:

fun findMinMax (LEAF v) = (v, v)
  | findMinMax (NODE (left, right)) =
    let val (minLeft, maxLeft) = findMinMax left
        val (minRight, maxRight) = findMinMax right
    in (Int.min (minLeft, minRight), Int.max(maxLeft, maxRight))
    end