We'll begin class by looking at a Python library designed to be an aide in the study of binary trees.

You will then have the rest of class and homework time to work on your BST class in Ruby, which implements the methods described last class.

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 binary ssearch tree class (BSTwith 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. Working with your partner, complete the following exercises on paper by hand: Binary Trees By Hand. Submit one paper per pair at the end of class for your first 4th quarter grade.