datatype IntTree = Empty | Node of int * IntTree * IntTree;

fun add(Empty, n) = Node(n, Empty, Empty)
|   add(Node(data, left, right), n) =
	if n <= data then Node(data, add(left, n), right)
	else Node(data, left, add(right, n));

fun addAll([]) = Empty
|   addAll(first::rest) = add(addAll(rest), first);

fun height(Empty) = 0
|   height(Node(_, left, right)) = 1 + 
        Int.max(height(left), height(right));

fun contains(Empty, n) = false
|   contains(Node(data, left, right), n) =
        if n = data then true
        else if n < data then contains(left, n)
        else contains(right, n);

fun contains(Empty, _) = false
|   contains(Node(data, left, right), n) =
        n = data orelse (n < data andalso contains(left, n))
                 orelse contains(right, n);

fun max(Empty) = NONE
|   max(Node(data, _, Empty)) = SOME data
|   max(Node(_, _, right)) = max(right);

fun printTree(Empty) = ()
|   printTree(Node(data, left, right)) = (
        printTree(left);
        print(Int.toString(data) ^ "\n");
        printTree(right)
    );

fun printTree2(t) =
    let
        fun printHelper(Empty, _) = ()
        |   printHelper(Node(data, left, right), indent) = (
                printHelper(left,  indent ^ "    ");
                print(indent ^ Int.toString(data) ^ "\n");
                printHelper(right, indent ^ "    ")
            );
    in
        printHelper(t, "")
    end;

fun removeLeaves(Empty) = Empty
|   removeLeaves(Node(data, Empty, Empty)) = Empty
|   removeLeaves(Node(data, left, right)) =
        Node(data, removeLeaves(left), removeLeaves(right));
	     
fun collapse(Empty) = []
|   collapse(Node(data, left, right)) = 
	 collapse(left) @ data::collapse(right);

fun treeMap(f, Empty)= Empty
|   treeMap(f, Node(data, left, right)) =
	Node(f(data), treeMap(f, left), treeMap(f, right));


(* test tree data *)
val t = add(Empty, 42);
val t = add(t, 27);
val t = add(t, 19);
val t = add(t, 40);
val t = add(t, 41);
val t = add(t, 37);
val t = add(t, 55);
val t = add(t, 99);
val t = add(t, 77);
val t = add(t, 83);