Our task will be to implement a binary search tree in Ruby. You will work in the following pairs to complete this project:

• Anar and Adonis
• Akshay and Cody
• Luis and Mulbah
• Ved and Turner
• Jamethiel and Caleb
• Isaac and Marin
• Anfal and Trostin
• Parker and Johan

These pairs were not random, but were instead intentionally choosen by me as clique breakers with an eye toward combating Senioritis and enhancing productivity. We'll see how well I did ;-)

We want to create a BinarySearchTree class with the following methods:

• insert(value): Inserts a value into the BST
• search(value): Returns true if value exists in the tree
• delete(value): Removes a value from the tree
• in_order_traversal: Returns array of values in sorted order
• pre_order_traversal: Returns array in root-left-right order
• post_order_traversal: Returns array in left-right-root order
• min: Returns the minimum value
• max: Returns the maximum value
• height: Returns the height of the tree
• empty?: Returns true if tree has no nodes

Before you can implement these in code, you should practice doing them on paper by hand. We will use class time today to do just that.