Delete a Value From a BST

Complete remove(Node node, int value) and its helper minValue(Node node) so tree.remove(value) takes value out of the tree and leaves a tree that still follows the BST rule. Removing a value that is not in the tree changes nothing.

Reminder: the three cases of removing from a BST. In a binary search tree every value in a node's left subtree is smaller than the node, and every value in its right subtree is larger. Finding the node works just like a search: go left when the value is smaller, right when it is larger. What happens once you find it depends on how many children it has: 1. A leaf (no children) simply disappears. 2. A node with one child is replaced by that child, which moves up into its place. 3. A node with two children keeps its place but takes a new value: its in-order successor, the smallest value in its right subtree (go right once, then left as far as you can). Then that successor is removed from the right subtree, which is always case 1 or case 2 because the successor has no left child.

remove(50):      50                60
                /  \              /  \
              30    70    ->    30    70
                   /  \                 \
                 60    80                80

Write remove the same way insert is written: it returns the root of the subtree it was given, and each caller stores the result back in its link, as in node.left = remove(node.left, value). That is how a parent lets go of a removed child, and how case 2 moves the child up into place.

Requirements: 1. remove(Node node, int value) returns null for an empty subtree, searches left or right, handles the three cases at the matching node, and returns the node that should now sit in this spot. 2. For two children, get the successor with minValue(node.right), copy it into the node, then remove that value from node.right. 3. minValue(Node node) returns the smallest value in the subtree that starts at node. It is only ever called on a subtree that is not empty. 4. Do not change insert, the public remove(int value) or preOrder(). The tests print the pre-order after each removal to check the shape of the tree.

The Node class is provided - do not rename it and do not add public to it, because a Java source file may contain only one public class.

Do NOT write a main method.