In this task, you will implement the following specs.

The ratings.datastructures. BinaryTreeNode class that has been provided in the handout repo. An object of this

type will be returned by one of your methods and will be tested in Autolab. Just like the LinkedListNode class, all

these methods must exist and be named exactly as they are in the repo or there will be errors during grading. You may

add additional methods to this $\frac{\frac{?}{?}}{?}$ class, but don't call those methods from your tests.

Create a Playlist class in the ratings package with the following functionality. This class will use a Binary Search Tree $($BST$)$

to store a playlist of Songs in sorted order. This class will have the following behavior:

A constructor that takes a Comparator of Songs

You will use this Comparator in a BST to sort the songs that are added to the playlist. You should create and

initialize any instance variables you'll need when this constructor is called

A method named addSong that takes a reference to a Song and returns void

This method will add the song to the playlist by inserting it into a BST with the comparator from the constructor

Note: You are allowed to use the BST code provided in lecture

A method named getSongTree that takes no parameters and returns the BinaryTreeNode of Songs that is the root

node of your BST$.$ This method should be a simple getter with one line of code

A method named getSongList that takes a BinaryTreeNode of Songs as a parameter and returns a

LinkedListNode of Songs

This method traverses the tree from the parameter and returns all the songs in the tree in a Linked List in sorted

order $($Assuming the parameter is the root of a BST$)$

Note: This method is expected to contain the majority of the difficulty of this task

It's recommended that you write the next method before this one

A method named getSongList that takes no parameters and returns a LinkedListNode of Songs

This method traverses your BST and returns all the Songs in the tree in a Linked List in sorted order

This method should be one line since you can call your other getSongList method with the root of your BST as

the argument

This is the method that you will test in this task. You should write this method while writing the other

getSongList method so you can run your tests and utilize the debugger while writing your code

The returned node will be the head of a linked list containing all the Songs that were added in sorted order

according to the comparator provided to the constructor

Example: If you provided a SongTitleComparator, the songs will be sorted alphabetically

Example: If you provided a SongBayesianRatingComparator $,$ the songs will be sorted in decreasing order $($The

highest rated songs first$)$ according to their bayesian average rating with $2$ fake ratings of $3$ being added.

If no songs have been added to the Playlist, this method returns null to represent an empty linked list