(* Code for Lecture 5: Datatypes                         *)

(************************************************************************)

datatype 'a tree = Empty | Node of 'a * 'a tree * 'a tree

(* size of a tree
   size: 'a tree -> int

   size(T) = n where n is size of the tree determined by
   the number of nodes. 
*)
fun size (Empty) = 0
  | size (Node(a, L, R)) = 
  size(L) + size(R) + 1


(* insert: (int * 'b) -> (int * 'b) tree -> (int * 'b) tree 
   
   insert (x,d) T = T'  where (x,d) has been inserted into T
   and any previous occurrences of (x,d') in T have been
   overwritten
  
*)

fun insert (e as (x,d)) Empty = Node(e, Empty, Empty)
  | insert (e as (x,d)) (Node((y,d'), L, R)) = 
  if x = y 
    then Node(e, L, R) 
  else 
    (if x < y then 
       Node((y,d'), insert e L, R)
     else 
       Node((y,d'), L, insert e R))

(* lookup : int -> (int * 'b) tree -> 'b option 
   
   lookup x T = 
   
   if there exists a node in T with key x and data d,
   then return SOME(d) else NONE

   NOTE: Although the type of this function is polymorphic
   in 'a and 'b, it depends on the fact that we do have
   functions to compare elements of type 'a!

*)
fun lookup x Empty = NONE
  | lookup x (Node((y,d), L, R)) = 
  if x = y then SOME(d)
    else
      (if x < y then lookup x L
	 else lookup x R)

(* NOTE: We enforce the property : 
    lookup x (insert (x,d) t) = SOME(d)
*)



(************************************************************************)
(* Examples of trees *)

val t1 = Node(9, Node(3, Node(2, Empty, Empty),
		         Node(5, Node(4, Empty, Empty), Node(6, Empty, Empty))), 
	         Node(13, Node(11, Empty, Empty), Node(15, Empty, Empty)));


(*             9
            /     \
           3       13
         /  \     /  \ 
        2    5   11   15
            / \
           4   6
*)