In this laboratory assignment, you will write an OCaml function that deletes a node from a binary search tree (BST). so it is assumed that you are familiar with the BST deletion algorithm.

We will begin by briefly reviewing BSTs. A BST is a binary tree with zero or more nodes. A BST with zero nodes is said to be empty. Each node in a non-empty BST has a key, a left subtree, and a right subtree. The keys are totally ordered, so that if k and k are keys, then either k < k, or k > k, or k = k. The left subtree and right subtree are other BSTs, which may be empty or non-empty. Now suppose that k is the key at the root of a BST. Then all nodes in the roots left subtree have keys less than k, and all nodes in the roots right subtree have keys greater than k. This is the BST property. As a result of the BST property, a key cannot appear in a BST more than once. For example, the following diagram shows a tree that satisfies the BST property. Its keys are integers. Empty subtrees are shown with slashed boxes, and non-empty subtrees are shown with arrows.

The BST property lets us efficiently search a BST for a key, and it lets us efficiently add a new node (with a new key) to a BST. It also lets us efficiently delete a node from a BST, given its key. In this laboratory, you must write an OCaml function that efficiently deletes a node from a BST in a way that preserves the BST property.

2. Implementation.

You must first define an OCaml type 'key bst that describes a binary search tree whose keys have the type 'key. Here is how to do that:

type 'key bst = BstEmpty | BstNode of 'key 'key bst 'key bst ;;

The type 'key may be any OCaml type; all keys in a BST have the same type. The constructor BstEmpty returns an empty BST. The constructor BstNode(k, l, r) returns a non-empty BST with a node at its root. Here k is the roots key, of type 'key; l is the roots left subtree, of type 'key bst; and r is the roots right subtree, also of type 'key bst. (A real binary search tree would also have a value in each node, but we do not care about values here.) Using BstEmpty and BstNode, you must define an OCaml function bstDelete tree key, where tree has the type 'a bst, and key has the type 'a. The function itself has the type 'a bst -> 'a -> 'a bst. You may assume that tree satisfies the BST property. Your function must return a BST that is like tree, and that satisfies the BST property, but in which the node containing key has been deleted. The node containing key may appear anywhere in tree. There are at least five different cases that bstDelete must handle correctly:

• Deleting a key from an empty BST.

• Deleting a key from a BST whose root has empty left and right subtrees.

• Deleting a key from a BST whose root has an empty left subtree, and a non-empty right subtree.

• Deleting a key from a BST whose root has a non-empty left subtree, and an empty right subtree.

• Deleting a key from a BST whose root has a non-empty left subtree, and a non-empty right subtree.

Here are some hints. First, since bstDelete cannot use mutable data structures, it must return a copy of tree in which the node containing key does not appear. For efficiency, it must not copy all the nodes of tree! It must copy only the nodes that are necessary. If tree is well-balanced and has n > 0 nodes, then bstDelete must work in O(log n) time. Second, it is not an error if a node containing key never appears in tree! If that happens, then bstDelete must return either tree, or else a copy of treeas described in the previous hint. Third, the cases shown above can be implemented using OCamls matchwith mechanism. Each case will have an expression involving BstEmpty and/or BstNode on the left of the arrow ->. Most cases will have an ifthenelse on the right of the arrow. Fourth, many of the cases will involve recursive calls. They need not all be tail recursions. Maybe none of them will be! It is impossible (or at least hard) to write bstDelete in a completely tail-recursive way. Fifth, for the last case, you must write a helper function bstMaxKey tree that returns the maximum key in tree, whose type is 'a bst. It must therefore have the type 'a bst -> 'a. To find the maximum key, bstMaxKey must move right through tree as deeply as it can, until it finds the rightmost node. It then returns the key in that node. It must raise the exception BadEmptyBst if tree is empty, but that should never happen.

test code right there :

type 'key bst = BstEmpty | BstNode of 'key * 'key bst * 'key bst ;;

let bstInsert tree key =

let rec inserting subtree =

match subtree

with BstEmpty -> BstNode(key, BstEmpty, BstEmpty) |

BstNode(otherKey, leftSubtree, rightSubtree) ->

if key < otherKey

then BstNode(otherKey, inserting leftSubtree, rightSubtree)

else if key > otherKey

then BstNode(otherKey, leftSubtree, inserting rightSubtree)

else subtree

in inserting tree ;;

let bstIsIn key tree =

let rec isInning subtree =

match subtree

with BstEmpty -> false |

BstNode(otherKey, leftSubtree, rightSubtree) ->

if key < otherKey

then isInning leftSubtree

else if key > otherKey

then isInning rightSubtree

else true

in isInning tree ;;

let t = BstEmpty ;;

let t = bstInsert t 100 ;;

let t = bstInsert t 70 ;;

let t = bstInsert t 137 ;;

let t = bstInsert t 53 ;;

let t = bstInsert t 86 ;;

let t = bstInsert t 74 ;;

let t = bstInsert t 212 ;;

let t = bstInsert t 149 ;;

let t = bstInsert t 997 ;;

(* This is the one we care about, but OCaml will indent it less clearly.

BstNode (100,

BstNode (70,

BstNode (53, BstEmpty, BstEmpty),

BstNode (86,

BstNode (74, BstEmpty, BstEmpty),

BstEmpty)),

BstNode (137,

BstEmpty,

BstNode (212,

BstNode (149, BstEmpty, BstEmpty),

BstNode (997, BstEmpty, BstEmpty)))) *)

let t = bstDelete t 149 ;;

(* 5 points if you get this.

BstNode (100,

BstNode (70,

BstNode (53, BstEmpty, BstEmpty),

BstNode (86,

BstNode (74, BstEmpty, BstEmpty),

BstEmpty)),

BstNode (137,

BstEmpty,

BstNode (212,

BstEmpty,

BstNode (997, BstEmpty, BstEmpty)))) *)

(* Delete a node from a right subtree, with no children. *)

let t = bstDelete t 997 ;;

(* 5 points if you get this.

BstNode (100,

BstNode (70,

BstNode (53, BstEmpty, BstEmpty),

BstNode (86,

BstNode (74, BstEmpty, BstEmpty),

BstEmpty)),

BstNode (137,

BstEmpty,

BstNode (212, BstEmpty, BstEmpty))) *)

(* Delete a node from a right subtree, with one child. *)

let t = bstDelete t 86 ;;

(* 5 points if you get this.

BstNode (100,

BstNode (70,

BstNode (53, BstEmpty, BstEmpty),

BstNode (74, BstEmpty, BstEmpty)),

BstNode (137,

BstEmpty,

BstNode (212, BstEmpty, BstEmpty))) *)

(* Delete a node with two children. *)

let t = bstDelete t 100 ;;

(* 10 points if you get this. I'm assuming you replaced 100 with the largest

key 74 in the left subtree, then deleted its node.

BstNode (74,

BstNode (70,

BstNode (53, BstEmpty, BstEmpty),

BstEmpty),

BstNode (137,

BstEmpty,

BstNode (212, BstEmpty, BstEmpty))) *)

(* Delete a node from the left subtree, with one child. *)

let t = bstDelete t 70 ;;

(* 5 points if you get this.

BstNode (74,

BstNode (53, BstEmpty, BstEmpty),

BstNode (137,

BstEmpty,

BstNode (212, BstEmpty, BstEmpty))) *)

(* Delete a node from the right subtree, with one child. *)

let t = bstDelete t 137 ;;

(* 5 points if you get this.

BstNode (74,

BstNode (53, BstEmpty, BstEmpty),

BstNode (212, BstEmpty, BstEmpty)) *)

(* The big finish. Delete all the remaining nodes! *)

let t = bstDelete t 53 ;;

let t = bstDelete t 212 ;;

let t = bstDelete t 74 ;;