# Binary Search Trees

The definition of a binary search tree (BST) is similar to that of a binary tree, with one important difference:

A binary search tree is either:
1.  an empty tree; or
2.  a node, called a root, and two children, left and right, each of which is itself a binary search tree.  Each node contains a value such that the value at the root is greater than the value in any of the nodes in the left subtree, and less than or equal to the value of any nodes in the right subtree.  (Berman, "Data Structures via C++:Objects by Evolution", 1997.)

An example of a binary search tree appears below.

Note: the definition above is not exactly the same as the version in Lewis & Chase.  Alternative definitions for binary search trees  handle duplicates in various ways.  The definition above specifies that any duplicates must appear in the right subtree.  Some definitions specify that any duplicates must appear in the left subtree (all nodes in the left subtree are less than or equal to the root and all nodes in the right subtree are greater than the root).  Still others, like the one in our textbok, do not allow duplicates at all, specifying that all nodes in the left subtree are less than the root and all nodes in the right subtree are greater than the root.  Thus, any BST implementation must specify how (and whether) it handles duplicates.

## Mini Lab

### Inserting into a Binary Search Tree

How would you insert an element in a binary search tree?  You know that for every tree, the values in the right subtree are all greater than or equal to the value of the root and the values in the left subtree are less than the value of the root.  Thus, if the value to be inserted is less than the value in the root node, the new value belongs in the left subtree.  If the value to be inserted is greater than or equal to the value in the root node, the new value belongs in the right subtree.  This leads to a nice recursive method for inserting an element in a binary search tree.  If the tree is empty, insert the value there.  Otherwise, if the value is less than the current node, insert the value in the left subtree.  Otherwise, insert the value in the right subtree. Since we need to compare values in a binary search tree, all objects inserted in a binary search tree should be `Comparable`.

1. Create a `BST` class.  A binary search tree is a specialized binary tree.  Technically it is not a subtype of a binary tree, because one can add any type of object to a binary tree, whereas one should only add `Comparable` objects to a binary search tree. For our purposes, though, we will consider it OK to create a `BST` class as an extension of the `BinaryTree` class.
2. Redefine the `add` method in the `BST` class to add an element to the correct spot in the binary search tree.  Remember that the `add` method takes an `Object` parameter.  In order to find the correct spot, you will have to cast the `Object` parameter to a `Comparable`.   Document the redefined method well, including the precondition that the parameter object must be `Comparable`.
3. Before testing your method, read it over carefully and develop drawings that illustrate the various steps in the algorithm.  Recursion can be tricky, but illustrating the process can be useful.  Then test the method.   You  may find the `Debug` class helpful.

### Deleting from a Binary Search Tree

Implement the following methods:

1. `leftmost` -- Private method that returns the value of the left-most node in a tree. (Which extreme value in the tree does this method return?)
2. `removeLeftmost` -- Private method that removes the left-most node in a tree and returns the value that was in that node; returns null if the tree is empty.  If the left-most node has a right child, this method "removes" the left-most node by replacing its data value and left and right subtree references with those from the root of the right child.   (It must first save a copy of the original data value, though, so that it can return it.) At some point the root of what used to be the right subtree will be garbage-collected, since there is no longer a reference to it from the left-most node.  Once you have this method working you can remove the `leftmost` method.
3. `remove` -- Takes a `Comparable` as a parameter (or an `Object` which you would then cast to `Comparable`) and removes it from the BST.  If the node was a leaf, it becomes an empty tree by setting its data value and left and right subtree references all to null.  If the node has a non-empty right subtree, its value should be replaced with the smallest value in the right subtree, which should be removed from the subtree. What should the method do if the node whose value is being removed is not a leaf but has an empty right subtree?
This method returns `true` if the object was in the tree (and was removed), or `false` if the object was not in the tree.

Is this an appropriate way to delete from a binary search tree?  Does it preserve the BST properties of the tree?  How does it preserve them, or how are they violated?

### Other BST operations

The `equals` method must be redefined for the `BST` class.  Identify any other `BinaryTree` methods that must be redefined.

1. `equals` -- takes an `Object` as a parameter and returns `true` if it is a `BST` and is equal to this binary search tree; two binary search trees are equal if they contain the same nodes (and the same number of each node)  (NOTE: whenever you redefine the `equals` method, you should also redefine the `hashCode` method; in this case, you may redefine it to throw an `UnsupportedMethodException`.)
2. Redefine other `BinaryTree` methods in the `BST` class as necessary.
3. Implement a static `isBST` method in the `BinaryTreeLab` class that takes a binary tree as a parameter and returns `true` if the tree is a binary search tree and `false` if it is not a binary search tree.  Remember that an empty binary tree is a valid binary search tree.   You may find it useful to use the `ExtremeValueCalculator` class from the Binary Tree Lab. The precondition for `isBST` is that all the objects in the binary tree must be `Comparable`.

Authors: Autumn C. Spaulding autumn@max.c.skzoo.edu