In this lab, we will implement a Binary Search Tree and visualize the processes of insertion, deletion, and rotation.

- IntelliJ
- Lab partner

- Download the skeleton for this project.
- Unpack the code into a new IntelliJ Java project.

We can efficiently store information with arrays and linked lists, but
determining if an element is present could take a linear search through
each element if the data is not sorted. At best, sorting will take *O(n
log n)*, and so we explore an alternative here which incorporates the
idea of binary search into a linked structure of nodes.

`Optional`

vs `null`

One way to implement a `TreeNode`

in Java is to use `null`

for the `left`

and `right`

children when these children are empty. However, this opens up
the possibility for a `NullPointerException`

if we code incorrectly, and
we won’t know if the exception is because of this or some other
unexpected `null`

in our algorithm.

In this lab, we will use a special class in Java called `Optional`

. This
class can be used in lieu of `null`

, so you know exactly what error you are
getting and why. We wrap all of our `TreeNode`

objects in an
`Optional`

object. So, instead of saying `left == null`

, we would
ask ‘left.isPresent()’. If `left`

exists, then we can get the `TreeNode`

by
saying `left.get()`

.

`left = Optional.of(new TreeNode(value))`

.
Methods that remain to be implemented in the `TreeNode`

class have been
marked with TODO for easy identification.

`insert()`

and `contains()`

Use recursion to complete the `insert()`

and `contains()`

methods in the `TreeNode`

class. Both of them will need to use the result of `value.compareTo(this.value)`

method
to determine if the parameter is less than, equal to, or greater than the value
at the current `TreeNode`

.

The test case `BinarySearchTreeTester.test1()`

should pass if
your solutions are correct.

Complete the `size()`

, `getMin()`

, `getMax()`

, and `height()`

methods in
the `TreeNode`

class.

Then run `BinaryTreeApp`

. As you insert nodes into your
tree, you should see the statistics updated on the right. Make sure the
values are correct by experimenting with different tree structures.

Complete the `preOrder()`

, `postOrder()`

, and `inOrder()`

methods in the
`TreeNode`

class. The `op`

parameter is a `Consumer`

object that performs
the `op.accept(value)`

operation on the current value either before, after,
or in-between using recursion to traverse the children.

These methods should pass their unit tests, and also you
can test them in `BinaryTreeApp`

.

Implement the `remove()`

method. Note that it does not return the
removed node; it returns the node upon which it was invoked, and
rebuilds the tree as it exits from its recursive calls. Follow the
comments carefully.

`left = left.get().remove(target);`

It should pass its unit tests and again is testable on the GUI, by clicking on nodes you wish to remove.

Implement left and right rotations. When correct, they should pass their
unit tests, and you can also test them in the GUI by clicking on the
node that you wish to rotate. As with `remove()`

, these methods return
the rebuilt tree nodes.

Create trees with 3, 7, and 15 nodes. First, create a balanced tree. Next, erase the tree and create a degenerate tree that is completely linear. Then, use rotations to transform each linear tree into a balanced tree. Record in your evaluation document the number of rotations you needed to perform to balance each tree. Discuss how you identified the need for a rotation when examining each tree.

Submit `TreeNode.java`

and your evaluation document via Teams.

- To
**Partially Complete**this lab, complete Steps 1, 2, and 3. - To
**Complete**this lab, do the above and Steps 4, 5, and 6.