Binary Search Trees MINI-LAB

By Autumn C. Spaulding with Alyce Brady

Definition of a Binary Search Tree

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

An example of a binary search tree appears below.

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 left subtree are less than the value of the root and the values in the right subtree are all greater than or equal to 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. In other words, the type T for the objects in a binary search tree must extend Comparable.

1. Download the incomplete K_BST.java and BSTLab.java classes. K_BST.java is a skeleton version of your eventual binary search tree class. BSTLab.java is a test driver similar to BinaryTreeLab.java, but to test binary search trees.
2. Read over the two files, especially K_BST.java. We are going to consider a binary search tree to be a specific type of binary tree, so a binary search tree IS-A binary tree. Note that the syntax for defining it as a subclass of K_AbstRecBinTree includes the restriction that objects in a BST must be of a type T that extends Comparable.
3. Redefine the add method in the K_BST class to add an element to the correct spot in the binary search tree.
4. 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 data value from 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 value of type T as a parameter and removes it from the BST. First it steps through the tree recursively until it finds the node to remove. Note that, unlike many of the recursive functions in K_AbstRecBinTree, you don't have to traverse both the left and right children of any given node to see if the value to remove is there; if it isn't the current node, you will always know whether it would be in the left or right child.

   Once you find the node to remove, you need to determine whether it was a leaf, so you can just remove it (replace its data value and left/right subtrees with null, making it an empty tree), or whether you need to replace it with something else. If there are some values in the right subtree (the node has a non-empty right subtree), then we can replace the value being removed with the smallest value in the right subtree, since that will preserve the BST invariant. This also means deleting the smallest value in the right subtree. If there is nothing in the right subtree (but we already determined this node is not a leaf, then we can just slide the data and links up from the left subtree to the current node. This method returns true if the object was in the tree (and was removed), or false if the object was not in the tree.

   Stop and Think What should the method do if the node whose value is being removed is not a leaf but has an empty right subtree?
   

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?

Have fun! And if you have any questions remember I am available through email, Teams, and my office hours. And don't forget the Collaboration Center, which is a great place to work and ask questions too!