(* bintree.sml -- an SML implementation of
   simple binary search trees *)

(* A tree is either empty, or a node with a
   key and references to two other trees. *)

datatype tree
  = EMPTY
  | NODE of {key: int, left: tree, right: tree}

(* Print the keys in a tree, using an
   inorder traversal: left, key, right. *)

fun printTree(tree) =
  case tree
    of EMPTY => ()
     | NODE{key,left,right} =>
	(printTree(left);
	 print(Int.toString(key)); print "\n";
	 printTree(right))

(* Insert a key in a tree and return the new tree. *)

fun insert(tree, newKey) =
  case tree
    of EMPTY =>
	NODE{key=newKey, left=EMPTY, right=EMPTY}
     | NODE{key,left,right} =>
	if newKey < key then
	  NODE{key=key, right=right,
	       left=insert(left, newKey)}
	else if newKey > key then
	  NODE{key=key, left=left,
	       right=insert(right, newKey)}
	else (* key = newKey *)
	  tree

(* Sort and print a list of integers using a binary tree. *)

fun sortAndPrint2(intList, tree) =
  case intList
    of [] => printTree(tree)
     | first::rest =>
	sortAndPrint2(rest, insert(tree, first))

fun sortAndPrint(intList) =
  sortAndPrint2(intList, EMPTY)