CSE 130 Fall 2011 - In-Class Exercise 4

Suppose you are given a polymorphic ML datatype

type ('a, 'b) bst = Leaf | Node of 'a * 'b * ('a, 'b) bst * ('a, 'b) bst

that represents Binary Search Trees where:

1. each node is of the form Node (key, value, left, right)
2. each Node(key',_,_,_) in the left subtree is such that key' < key
3. each Node(key',_,_,_) in the right subtree is such that key < key'

Write two functions

val lookup: 'a -> ('a, 'b) bst -> 'b option
val insert: 'a -> 'b -> ('a, 'b) bst -> ('a, 'b) bst