How to find the minimum and maximum values of the BST given below?-CodePudding

Below is the code I currently have. Not sure if it is even right, but the datatype line MUST remain the same. I am trying to create a getMin and getMax function. Below will be the requirements for it.

datatype tree = leaf | node of int * tree * tree;

fun isEmpty leaf = if leaf=nil then true else false;

fun inorder leaf = nil
  | inorder (node(key,left,right)) = inorder left @ [key] @ inorder right;

fun preorder leaf = nil
  | preorder (node(key,left,right)) = preorder left @ preorder right @ [key];

fun postorder leaf = nil
  | postorder (node(key,left,right)) = [key] @ preorder right @ preorder left;

(* Inputs a BST. Returns the smallest value in the tree. If the tree is empty, the function should return NONE. *)
    getMin : tree -> int option

(* Inputs a BST. Returns the largest value in the tree. If the tree is empty, the function should return NONE. *)
    getMax : tree -> int option

Any help with this will be greatly appreciated. Thanks!

CodePudding user response：

fun isLeaf (node(_, _, _)) = false
  | isLeaf leaf = true;

fun getMin(node(x, left, _)) =
    if isLeaf left then x
    else getMin left
  | getMin leaf = raise Empty;

fun getMax(node(x,_,right)) =
    if isLeaf right then x
    else getMax right
  | getMax leaf = raise Empty;

CodePudding user response：

Think this through. A tree is either a leaf or a node. A node contains a value and two other trees.

What is the maximum value of a leaf? It doesn't have a value, so it's NONE.

What's the maximum value of a node? Well, it's the maximum of either:

Its value.
The maximum value of its left branch.
Or, the maximum value of its right branch.

How do you find the maximum value of three int option values? One way might be:

fun max(NONE,   NONE,   NONE)   = NONE
  | max(SOME a, NONE,   NONE)   = SOME a
  | max(NONE,   SOME b, NONE)   = SOME b
  | max(NONE,   NONE,   SOME c) = SOME c
  | max(SOME a, SOME b, NONE)   = if a > b then SOME a else SOME b
  | max(SOME a, NONE,   SOME c) = if a > c then SOME a else SOME c
  | max(NONE,   SOME b, SOME c) = if b > c then SOME b else SOME c
  | max(SOME a, SOME b, SOME c) = 
    if a > b andalso a > c then SOME a
    else if b > a andalso b > c then SOME b
    else SOME c