1.1 This simple program implements persistent functional binary search
trees, so that if tree2-insert(x,tree1), then tree1 is till available
for lookups even while tree2 can be used.

type key = string
datatype tree = LEAF | TREE of tree * key * tree

val empty = LEAF

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

a. implement a `member` function that returns `true` if the item is
found, else `false`

b. Extend the program to include not just membership, but the mapping
of keys to bindings:

datatype 'a tree = ...
insert: 'a tree * key * 'a -> 'a tree
lookup: 'a tree * key -> 'a

c. These trees are not balanced; demonstrate the behavior on the
following two sequences of insertions:
   (a) t s p i p f b s t
   (b) a b c d e f g h i

d*. Research balanced search trees in Sedgewick [1997] and recommend a
balanced-tree data structure for functional symbol tables. Hint: To
preserve a functional style, the algorithm should be one that
rebalances on insertion but not on lookup, so a data structure such as
splay trees is not appropriate.