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: 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 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.

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.
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. You will also need to cast the left and right subtrees to BST in order to get the right add method in the recursive calls.
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:

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?)
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.
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 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.

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.)
Redefine other BinaryTree methods in the BST class as necessary.
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
and Alyce Brady abrady@kzoo.edu