(* functions from the lecture notes *)
datatype 'a tree = Lf
                 | Br of 'a * 'a tree * 'a tree

fun count Lf = 0
  | count (Br(v,t1,t2)) = 1 + count t1 + count t2


exception Missing of string

fun lookup (Br ((a,x),t1,t2), b) =
      if      b < a then  lookup(t1, b)
      else if a < b then  lookup(t2, b)
      else x
  | lookup (Lf, b) = raise Missing b

fun update (Lf, b:string, y) = Br((b,y), Lf, Lf)
  | update (Br((a,x),t1,t2), b, y) =
		if b<a
		then Br ((a,x), update(t1,b,y), t2) else
		if a<b
		then Br ((a,x), t1, update(t2,b,y)) else (*a=b*) Br ((a,y),t1,t2)

fun preord (Lf, vs) = vs
  | preord (Br(v,t1,t2), vs) = v :: preord (t1, preord (t2, vs))


(* sorted return true is the items of the list are sorted *)
fun sorted [] = true
|	sorted [x] = true
|	sorted (x::y::zs) = (x<y) andalso sorted(y::zs)

(* check_tree returns true when given a valid binary search tree *)
fun check_tree b = sorted(List.map (fn (x,y) => x) (preord b))        


(* some trees for you to plat with *)
val test1 = Lf
val test2 = Br (("Alice", 6), Lf, Lf)
val test3 = Br (("Gerald", 8), Br (("Alice", 6), Lf, Lf), Br (("Lucy", 9), Lf, Lf))
val test3 = Br(("Alice", 6), Lf, Br(("Tobias", 2), Br(("Gerald", 8), Lf, Br(("Lucy", 9), Lf, Lf)), Lf))	

val test4 = Br
    (("Alice", 6), Br (("Abi", 11), Lf, Lf),
     Br (("Tobias", 2), Br (("Gerald", 8), Lf, Br (("Lucy", 9), Lf, Lf)), Lf))