(* 

BST

lookup: e x BST --> boolean
add:    e x BST --> BST
sum:        BST --> int
remove: e x BST --> BST
traverse:   BST --> int list

variables:
BSTs: M,N
elements: e,f

*)

datatype BST =
  empty |
  node of int * BST * BST;


exception lookupBST;
fun lookup(e,empty) = false
  | lookup(e,node(f,lt,rt)) = if e=f
				   then true
				   else
				     if e<f
				      then lookup(e,lt)
				      else lookup(e,rt) ;

fun add(e,empty) = node(e,empty,empty)
  | add(e,M as node(f,lt,rt)) = if e=f
				  then M
				  else 
				     if e<f
					then node(f,add(e,lt),rt)
					else node(f,lt,add(e,rt)) ;

fun sum(empty) = 0
  | sum(node(e,lt,rt)) = e+sum(lt)+sum(rt) ;

fun traverse(empty) = nil
  | traverse(node(e,lt,rt)) = [e]@traverse(lt)@traverse(rt) ;

exception remMinEmpty;

fun remMin(empty) = raise remMinEmpty
  | remMin(node(f,empty,rt)) = (f,rt)
  | remMin(node(e,lt,rt)) = let val (f,g) = remMin(lt)
				in (f,node(e,g,rt))
				end;

fun remove(e,empty) = empty
  | remove(e,node(f,lt,rt)) = if e<f
				then node(f,remove(e,lt),rt)
				else if e>f
				  then node(f,lt,remove(e,rt))
				else
				   if lt=empty then rt
				    else if rt = empty then lt
				    else let val (a,b)=remMin(rt)
					   in node(a,lt,b)
					   end;





val bst1 = empty;
val a = sum(bst1);
val bst2 = add(5,bst1);
val bst3 = add(10,bst2);
val b = sum(bst3);
val bst4 = remove(10,bst3);
val bst5 = add(7,bst4);
val t1 = traverse(bst5);