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 removeWordHelper() method below. The method signature is already given, do not modify these or add any new ones.

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 Word objects as their data – to have nodes with City data we can use BSTNode<Word> 

• 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 a node holds 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

addWord [PROVIDED]

This method is provided for you, and inserts a node containing a word and definition into the BST rooted at the instance variable “root”. It updates that instance variable if the tree is empty; otherwise it follows BST insertion rules to insert a node in its proper position.

This can be used to find the inorder successor of a target node, by calling findMin on the target’s right child.

DO NOT modify 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  (use compareTo to compare strings)

• Then, set curr’s left child, to removeWordHelper(curr.getLeft(), word)

Second Case: the target word is to the right of curr 

• Then, set curr’s right child, to removeWordHelper(curr.getRight(), word)

Final Case (when the target node is found):

• If curr has no children, 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 word/definition to be the same as the inorder successor you just found.
  • Set curr’s right child to be a recursive call to removeWordHelper(curr.getRight(), temp.getWord())
    • 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.