Overview

Binary search trees (BSTs) are recursive structures that start off at a node and then branch off into different levels. They store items using keys for comparison — you can’t have duplicate keys in a BST.  

Since there are different ways we can branch off in a BST, we can’t simply do a linear traversal like we have with arrays and linked lists. We’ll have to use algorithms that traverse deeper into the tree to find all nodes.

In this lab, your BST represents an actual tree (in New Jersey). Each BST node contains a Flower, symbolizing points on the tree. Each flower can either be empty OR contain a bug (butterfly, ladybug, or an invasive lanternfly). Since each bug has a unique heat signature, we can use this to identify bug types, and store them in the tree. For instance, a Flower with a heat signature of 16°C should be to the left of a Flower with a signature of 34°C (if 34°C is the root).

You will implement an add function and a Hibbard deletion to remove any lanternflies detected on the tree

Hibbard Deletion

When deleting from a BST, we need to decide how to handle the gap we create. In a linked list, we can simply fill in that gap with the next node. But BST nodes have two children, so which should we choose?

We can use a method called Hibbard Deletion, which says:

1. If a deleted node has no children, simply unhook it from its parent.
2. If a deleted node has one child, replace it with that child.
3. If a deleted node has two children, replace it with its in-order successor

• An in-order successor is the next node in sequence. i.e. the smallest node greater than the current node (aka the smallest node in the target’s right subtree)
• To find the inorder successor of a node: move once to the right, then as far left as possible.

i.e. In the example above, the inorder successor of 4 would be 5. This is because 5 is the smallest node in 4’s right subtree (aka the smallest node in the subtree starting with 9).

We can also see this by listing the entire tree in order traversal, then choosing the key directly after our target:

2 4 5 6 7 9 10 11 12

So after deleting the target, the tree would look like this:

Provided Classes

Bug.java is an enum class, which contains a few static values which we can reference. Such as Bug.LANTERNFLY, Bug.BUTTERFLY, Bug.LADYBUG, and Bug.EMPTY.

• It also contains the Bug.fromTemp(int temp) method, which will return the correct Bug type for a heat signature value.

Flower.java represents a single flower on the tree. Each flower can either hold a bug, or hold nothing. A flower has a heat signature, which can be used to determine which type of bug it holds (if any).

• Flowers are stored in BSTNodes, as the main data type for the Lanternflies BST

A BSTNode is a standard node within a Binary Search Tree-like the ones we’ve worked with during lecture. In this lab, we will work only with BSTNodes of type Flower, defined in Flower.java. 

Driver.java is a simple visualization class which can call your BST add/remove methods, and then display the resulting tree. You can use this to test your code, and determine if you are inserting/deleting properly.

Lanternflies.java This is the only file you will code in, and is the file you will submit to Autolab. Fill in the add() and remove() methods according to the descriptions below.

Working with BSTNode<> objects

For assignments/labs in CS112, we will use a cs112.jar file containing useful classes. This includes the BSTNode<> class, which implements a binary tree node. You’ve previously worked with the LLNode<> class to create linked lists. Many aspects of the BSTNode are similar:

• The BSTNode class takes in a generic type, which means it can store any type of data. In this lab you will be working with nodes that have Flower objects as their data – to have nodes with Flower data we can use BSTNode<Flower> 
• Making a node: BSTNode<T> newNode = new BSTNode<T>(data) — replace T with a type
  • Note that the data must be passed in for the constructor, and the data of a node can not be changed later (aka it is immutable). The data may not be null.
• Methods: 
  • getLeft() – returns the left child of the node
  • setLeft(BSTNode<T> left) – sets the left child of the node
  • getRight() – returns the right child of the node
  • setRight(BSTNode<T> right) – sets the right child of the node
  • getData() returns the data object a node holds

Directions

• DO NOT add new import statements.
• DO NOT add any new class attributes
• DO NOT change any of the method’s signatures.
• DO NOT modify the given constructor.

To complete this lab, you must implement the add() and remove() methods below.

To Run: run the following commands from the innermost Lanternflies directory, containing the src and bin folders.

1. Compile:
   1. Windows: javac -d bin -cp “lib/cs112.jar;lib/jgraphx.jar” src/tree/*.java
   2. Mac/Linux: javac -d bin -cp lib/cs112.jar:lib/jgraphx.jar src/tree/*.java
2. Run:
   1. Windows: java -cp “lib/cs112.jar;lib/jgraphx.jar;bin” tree.Driver
   2. Mac/Linux: java -cp bin:lib/cs112.jar:lib/jgraphx.jar tree.Driver

OR: Run through VSCode, ensuring you open the correct innermost Lanternflies directory

Make sure you are working from the correct directory: 

add(int heatSignature) 

The method takes in a parameter of type int. The type of flower node inserted into the BST will be reliant on the numerical value of this parameter, representing the flower’s heat signature.

• You can simply use the Bug.fromTemp(int temp) method to get the correct bug type for a heat signature. But these correspond to:
  • If the heat signature is less than 10 or greater than 40, the flower is empty
  • If the heat signature is greater than or equal to 11, and less than 20, then the flower contains ladybug
  • If the heat signature is greater than or equal to 20, and less or equal to 30, then the flower contains lanternfly
  • If the heat signature is greater than 30, and less than or equal to 40, then the flower contains a butterfly

Remember, we access the tree through the “root” instance variable, similar to the head of a linked list.

To Complete This Method:

1. Create the new flower and node:
   • Call Bug.fromTemp(heatSignature) to determine the bug type
   • Create a new Flower object with the heat signature and bug type
   • Wrap it in a new BSTNode
2. If the tree is empty (root is null), set the new node as the root and return
3. Else, traverse the tree to find insertion point:
   • Use a pointer starting at root
   • Use a while loop that continues until the correct position is found
   • At each node, compare heat signatures:
     • If the new node’s heat signature is less than the current node’s heat signature:
       • If the current node’s left child is null, insert the new node there and return
       • Otherwise, move the pointer to the left child
     • If the new node’s heat signature is greater than the current node’s heat signature:
       • If the current node’s right child is null, insert the new node there and return
       • Otherwise, move the pointer to the right child
     • If the heat signatures are equal, this is a duplicate — do nothing and return

remove(int heatSignature) [PROVIDED]

DO NOT EDIT. This is the recursive caller method for the deletion task. This method takes in a heat signature parameter to be removed. It will call upon the recursive remove() method you implement, in order to start deletion at the root..

remove(BSTNode curr, int heatSignature)

To complete this method:

We will create recursive cases to handle traversal and deletion.  You should use an if-elseif-elseif-else structure to fill out the following.

Base Case: if curr == null

• return null

First Case: the target word is to the left of curr (curr’s heatSignature > heatSignature)

• Then, set curr’s left child, to remove(curr.getLeft(), heatSignature)

Second Case: the target word is to the right of curr (curr’s heatSignature < heatSignature)

• Then, set curr’s right child, to remove(curr.getRight(), heatSignature)

Final Case (when the target node is found):

• If curr has no children (left and right are both null), return null.
• Else if curr’s left child is null, return the right child instead.
• Else if curr’s right child is null, return the left child instead.
• ELSE (when curr has both a left and a right child)
  • Get a pointer to the minimum node of curr’s right subtree (the inorder successor). You can do this by calling findMin() with curr’s right child.
  • Create a new temp BSTNode, and set its Flower to be the same as the inorder successor you just found.
  • Set curr’s right child to be a recursive call to remove(curr.getRight(), temp’s heatSignature)
  • This will delete the temp node from its original spot, allowing you to use it to replace your actual target.
  • Set your temp node’s left child to be curr’s left child
  • Set your temp node’s right child to be curr’s right child,
  • return temp

After all of the cases end, return curr.

findMin[PROVIDED]

DO NOT EDIT. This method takes in a BSTNode, and traverses it until the BSTNode with the lowest heat signature is found. This minimum BSTNode is returned.