Welcome to Lesson 12!

Learning Objectives
By the end of this class, you should know...
  • How do you implement the recursive BST operations
    • search
    • minimum
    • remove


1. Searching a BST
  • Searching a BST is an almost identical process to inserting a new node to the tree.
  • Let's review BST insert using an example, and then compare it to BST search:
  • We can thus adapt the insert pseudocode for search.
  • However, search returns a boolean to indicate whether the value was found, whereas insert is a void method.

Pseudocode for search helper(node, value)

1. Base Case: the value is equal to the node's data

1a. return true

2. Check if the value is smaller than the node's data.

2a. If this is true

2aa. If node's leftchild is null

2aaa. return false. The value was not found

2b. If the node's leftchild is not null

2bb. recursively call the search helper method passing it node's leftchild and value

3. Otherwise

3a. Check if the node's rightchild is null

3aa. If this is true, return false. The value was not found.

3b. If the node's rightchild is not null

3bb. recursively call the search helper method passing it node's rightchild and value




1.1. Writing the BST Search Method

  • Below is the code for the public search wrapper method
    public boolean search(T data) {
        if(root == null) {
            return false;
        } else {
            return search(data, root);
        }
    }
  • It is your job to write the helper method for search in your upcoming Lab.



2. Finding the Minimum Value in a BST
  • The purpose of the minimum method is to find the minimum value in the tree.
  • Where is the minimum value always located in a Binary Search Tree?
    • If you are uncertain, look at an example of BST to see where the minimum is located.
  • To find the minimum, all we need to do is to scroll through the nodes in the tree to the proper location.
Pseudocode for private minimum helper (Node node)
  • If the node's leftchild is not null
    • return recursive call to minimum, passing it node's leftchild
  • Otherwise
    • Return the node's data


3. Removing a Value from a BST
  • Remove is perhaps the most challenging BST algorithm to implement.
  • Like search, insert, and the tree traversals it is also recursive.
  • Remove works by first searching for a particular value in a BST.
  • Once the node has been located, it can then be removed.
  • However, complication comes from the fact that we could encounter several different cases:
    • Case 1: The node we wish to remove if a leaf node <-- easy case
    • Case 2: The node we wish to remove has only one child <-- medium case
    • Case 3: The node we wish to remove has two children <-- hard case
  • When deleting nodes in each of these cases, you must be mindful to preserve the BST property.
  • Let's look at each of these possibilities in the diagram below:
Deletion rules


  • Therefore, when writing remove, we need to handle all three cases.
  • The first 3 steps in the pseudocode below locate the value to remove inside the tree
  • Step 4 handles the three cases discussed above.
Pseudocode for remove helper(node, value)
  1. If node is null
    1. return node
  2. Otherwise, if value < the node's data
    1. set node's leftchild equal to the recursive call of remove helper on node's leftchild
  3. Otherwise, if value > the node's data
    1. set node's rightchild equal to the recursive call of remove helper on node's rightchild
  4. Otherwise,
    1. If node is a leaf node
      1. Set node to null
    2. Otherwise if node has a leftchild but no rightchild
      1. set the leftchild to be the node
    3. Otherwise if node has a rightchild but no leftchild
      1. set the rightchild to be the node
    4. Otherwise
      1. Search for the minimum value in the right subtree of the node
      2. Set the node's data to be the minimum value in the node's right subtree
      3. Set node's rightchild equal to the recursive call of remove helper, passing it node's rightchild and the minimum data of node's right subtree (i.e. delete the duplicate value in the right subtree)
  5. return the node

3.1 Writing BST Remove

  • Below is the signature for the public remove method (wrapper).
  • Note that the private minimum method can be used as a helper inside of the private remove method.
/**
     * Removes a value from the BST
     * @param data the value to remove
     * @precondition !isEmpty()
     * @precondition the data is located in the tree
     * @throws NoSuchElementException when the
     * precondition is violated
     */
    public void remove(T data) throws NoSuchElementException{}

3.2. Reflection: Tracing BST Remove

  • Redraw the below BSTs after the indicated value has been removed.
  • Make sure to draw any intermediary steps.
BST 1: Remove 18



BST 2: Remove




BST 3: Remove 15

https://helloacm.com/wp-content/uploads/2016/04/bst-tree-example.jpg

image source


Wrap Up
  • Answer the review questions on Canvas for today's lesson


Upcoming Assignments
  • Lab 6 due Monday
  • Study for your Quiz

~Have a Great Weekend!~