type key = string

datatype 'a tree = LEAF | TREE of 'a tree * (key * 'a) * 'a tree

val empty = LEAF


fun insert (LEAF, key, newval) = TREE(LEAF, (key, newval), LEAF)
  | insert (TREE(l,(k,v),r), key, newval) =
      if key < k
        then TREE(insert(l,key,newval),(k,v),r)
      else if key > k
        then TREE(l,(k,v),insert(r,key,newval))
      else TREE(l,(key,newval),r)

(* This is not exhaustive, and will fail if the tree 
   was not created using `insert` *)
fun lookup (TREE(l,(k,v),r), key) =
  if key = k
  then v
  else if key < k
  then lookup (l, key)
  else lookup (r, key)
  | lookup (LEAF, key) = raise Subscript