Week #10: Test and Mutating BST

Week #9 we had the second term test. It covered Trees including Binary Search Trees and it also covered Linked Lists. I discussed Binary Search Trees and Linked Lists in my previous blogs. Therefore refer to those for more information.

That week also learned about two important functions for mutating Binary Search Trees, insert and delete.

INSERT

This function inserts a new node into the Binary Search Tree and when it does so it must satisfy the conditions of a BST. These state that the data of the node must be comparable, the data in the left subtree must be less than that of the node and the data of the right subtree must be greater.

Here is the code (taken from class notes) for the function insert:

DELETE

The function delete, as its name states, it deletes a node from a Binary Search Tree. When deleting a node from a BST you must reconnect the remaining subtree. Here is the code (taken from class notes) for the function delete:

As demonstrated in the code, both functions use recursion to mutate the Binary Search Tree so that each node follows the appropriate criteria of BSNode.