I just need some help editing/finishing these functions that work on binary search trees in OCAML.

There are few that I just cannot seem to figure out. Thanks!

(* ssmap.ml: Provides types and functions for a map from string keys to string values. Internally uses a binary search tree sorted on the keys. Some functions must be completed. *)

open Printf;;

(* Algebraic type for a persistent binary search tree key/value mappings. *) type ssmap = | Empty (* no data: bottom of tree *) | Node of { (* node of anonymous record *) key : string; (* key for this node *) value : string; (* value associated with key *) left : ssmap; (* left branch *) right : ssmap; (* right branch *) } ;;

(* IMPLEMENT

val getopt : ssmap -> string -> string option

let opt = getopt map key in ...

Search the map for given key. If found, return the Some of the associated value. Otherwise return None. *) let rec getopt map key = match map with | Empty -> None | Node(node) -> let diff = String.compare key node.key in if diff = 0 then Some node.value else if diff < 0 then getopt node.left key else getopt node.right key

;;

(* IMPLEMENT

val contains_key : ssmap -> string -> bool

let present = contains_key map key in ...

Returns true if key is present in the map and false otherwise. Uses function getopt. *) let contains_key map str = if getopt map str = None then false else true ;;

(* IMPLEMENT

val iter : (string -> string -> unit) -> ssmap -> unit

let func key value = ... in

fold func map;

Apply func to all elements key/value pairs in the map for side-effects. Keys are visited in sorted order from minimum to maximum. Works as other iter-like functions such as List.iter or Array.iter. *) let rec iter func map = match map with | Empty -> () | Node(node) -> iter func node.left; func node.key node.value; iter func node.right; ;;

(* IMPLEMENT

val fold : ('a -> string -> string -> 'a) -> 'a -> ssmap -> 'a

let func cur key value = ... in

let reduction = fold func init map in ...

Apply func to all elements key/value pairs in the map to produce a single value at the end. Keys are visited in sorted order from minimum to maximum. Works as other fold-like functions such as List.fold_left or Array.fold_left. *) let rec fold func cur map = match map with | Empty -> cur | Node(node) -> if node.left = Empty then let next = func cur node.key node.value in fold func next map; else fold func cur node.left; fold func cur node.right; ;;

(* IMPLEMENT

to_string : ssmap -> string

let displaystr = to_string map in ...

Produces a string representation of the map. The format is

"[{k1 -> v1}, {k2 -> v2}, {k3 -> v4}]"

Key/vals appear from minimum key to maximum key in the output string. Functionality from the Buffer module is used with an in-order traversal to produce the string efficiently. May make use of a higher-order map function such as iter or fold. *) let to_string map = let buf = Buffer.create 256 in let rec build tree = match tree with | Empty -> () | Node(node) -> build node.left; let datastr = sprintf "{%s -> %s}, " node.key node.value in Buffer.add_string buf datastr; build node.right; in Buffer.add_string buf "["; build map; Buffer.add_string buf "]"; Buffer.contents buf ;;

(* IMPLEMENT

val findmin_keyval : ssmap -> (string * string)

let (minkey,minval) = findmin ssmap in ...

Find the "minimum" key in the given map and return it and its value as a pair. If used with an empty map, fails with exception message "No minimum in an empty tree". Since the map is based on a BST, the minimum key is at the left-most node. *) let rec findmin_keyval map = match map with | Empty -> failwith "No minimum in an empty tree" | Node(node) -> if node.left = Empty then (node.key, node.value) else findmin_keyval node.left ;;

(* IMPLEMENT

val remove_key : ssmap -> string -> ssmap

let newmap = remove map key in ...

Returns a new map without key in it. The internal tree is re-arranged according to standard BST conventions: (1) If key is a leaf, it is replaced with Empty, (2) If key is an internal node with one child, it's left or right branch replaces it, (3) If key is an internal node with both left/right children, it successor replaces it. Makes use of findmin_keyval to locate a succesor as the minimum of on the right child branch. *) let rec remove_key map key = match map with | Empty -> () | Node(node) -> let diff = String.compare key node.key in if diff = 0 then if node.left != Empty && node.right != Empty then let successor = findmin_keyval node.right in node.key = successor.key; remove_key map successor.key; else if node.left != Empty && node.right = Empty then node. else if diff < 0 then Node{node with left=(remove_key node.left key)} else Node{node with right=(remove_key node.right key)} ;;