BinarySearchTree "Smart" Remove

The current version of the cs20b.BinarySearchTree.BST class presented in class takes the approach of removing the "smallest of the biggest" values in the tree when BinarySearchTree::remove( Type value ) runs in the situation when the node being removed has two children. However, the mirror image approach (namely, the approach of removing the "biggest of the smallest" values) would also have worked.

Your task here is to make BinarySearchTree support a smarter remove operation, by making it choose to remove on the left or right subtree, depending on which side has a bigger height. By choosing that subtree to make the alteration, BinarySearchTree::remove( Type value ) hopefully can run faster, especially if the difference in the two heights is quite large. Removing from the right subtree is what the code currently does. Removing from the left subtree involves locating the "biggest of the smallest" values in that subtree.

The diagram below gives you my advice for how to proceed. See image.

Although you are certainly welcome to do it however you wish, here are some hints.

• First, ensure each BSTNode tracks its own height.
• Then, update BST's remove( ... ) function so that it doesn't blindly always pick to the "smallest of the biggest" but makes a smarter choice based on the BSTNode being removed. As it is now, in the 2-children case of remove, it performs node recycling and calls BinarySearchTree::removeMin( BinarySearchTreeNode ). To support the mirror image case, you'll likely need to create BST::removeMax( BinarySearchTreeNode ). In the 2-children case of remove, update the code so it uses removeMin when the right-side subtree has a larger height. However if the left-side subtree has a larger height, it should use removeMax on the left-side subtree.

Create a test driver program that exercises each of these methods, prints the tree and the results of each operation. For example, try testing your code with the following cases:

• insert 3, 5, 10, 6, 1
• print it with a LevelOrderIterator. Do you see all 5 nodes? Are they in the right place?
• remove 6 (this is the no-child case)
• print it with a LevelOrderIterator. Do you see all 4 nodes? Are they in the right place?
• insert 2, 8
• print it with a LevelOrderIterator. Do you see all 6 nodes? Are they in the right place?
• remove 10 (this is the one-child case)
• print it with a LevelOrderIterator. Do you see all 5 nodes? Are they in the right place?
• insert 9, 10
• remove 3 (this is the two-child case, with the left side having a shorter height)
• print it with a LevelOrderIterator. Do you see all 6 nodes? Are they in the right place?