PP $20\mathrm{.}5($page $801)$

Complete all missing methods in LinkedBinarySearchTree. Show test cases for all implemented methods being sure to include edge cases for methods where applicable.

Then, implement a balance tree method for this class using the brute force method described in Section $20\mathrm{.}5$ of your textbook.

Show test cases for two different degenerate trees, outputting the height of the tree before and after balancing the tree. Then, demonstrate insertions into a balanced tree that result in degenerate trees and rebalance the tree again.

Hint: Copy the elements into an ArrayList using an in$-$order traversal. Recursively build a balanced tree using a binary partitioning.