## Lecture 27 - Binary Trees Continued

As usual, create a directory to hold today's activities:

$mkdir ~/cs170/labs/lab27$ cd ~/cs170/labs/lab27


### Trees

You hopefully saw on Monday how we can build a binary tree following the rules of binary search. This is indicitive of how binary search is supposed to work: We know all of the relationships between all of the values in the tree. Today, we will see how that relationship applies to searching for values inside the tree as well. As you can imagine, it is related to how binary search works!

Lab Activity 1

Now we can finally see why we would use a Binary Tree, other than just building them and playing around with them. A tree of the form we have been building is called a "Binary Search Tree." Essentially, they are trees that have the ordering property defined on them. This should mean that Binary Search should work pretty well on a Binary Search Tree. Let's try it out.

#### Details

In your binary_tree.py file, write a new method in the BinarySearchTree class called search(self, data). This function should return True if data is in the binary tree, and False otherwise.

Again, there are two ways to accomplish this function: iteratively or recursively. Write any additional functions or methods you may need to accomplish your tasks. Write your estimation of the Big-Oh class of search, based on the number of nodes N in the tree, in the comments of your file.

#### Example

>>> my_list = [5, 3, 4, 8, 9]
>>> my_tree = BinarySearchTree()
>>> for element in my_list:
...     my_tree.insert(element)
>>> print(my_tree.search(5))
True
>>> print(my_tree.search(9))
True
>>> print(my_tree.search(10))
False
>>> print(my_tree.search(6))
False


#### Hint

• Binary search on a list involved finding the middle element of the list. Such an element doesn't quite exists in a tree. Instead, you are going to look at the data of the current element, to decide if you should explore down the left sub-tree, or the right sub-tree.

• If you are looking at a node that contains your data, then you have found the item. However, you only know the item isn't in the tree when you reach an empty node.

Lab Activity 2

We have added stuff to a binary search tree. However, we occasionally also need to be able to remove information from a binary search tree. Deletion of a leaf is very easy. Deletion of an internal node, however, is slightly more complicated.

#### Details

In your binary_tree.py file, write a new method in the BinarySearchTree class called delete(self, data). This function returns nothing. It only removes the node containing the data from the tree.

There are three cases for deleting a node N in the tree:

No Children
None should be put in place of N.
One Child
The remaining child should be put in place of N.
Two Children
Find the in-order successor of N in the tree. This is the left most value in the right sub tree of N. Place the successor value in the node N, then set the left child of N to be the result of recursively deleting successor starting at N.

Write a method called delete_helper(self, curr_node, data), which takes a node as a parameter as well. That is the node that all deletions will be done relative to. THIS METHOD SHOULD RETURN A NODE, which is the root of the tree that has had the information requested removed. This is similar to the "easier" method of inserting a node into a tree, as shown in class today.

#### Example

    my_list = [5, 3, 4, 1, 8, 7, 9]
my_tree = BinarySearchTree()
for element in my_list:
my_tree.insert(element)
print(my_tree.pre_order())
#5 3 1 4 8 7 9

my_tree.delete(4)
print(my_tree.pre_order())
#5 3 1 8 7 9

my_tree.delete(7)
print(my_tree.pre_order())
#5 3 1 8 9

my_tree.delete(3)
print(my_tree.pre_order())
#5 1 8 9

my_tree.delete(8)
print(my_tree.pre_order())
#5 1 9

my_tree.delete(5)
print(my_tree.pre_order())
#9 1


#### Hint

• Again, I hate thinking about this iteratively. But you could do it iteratively. My hints, however, will be about the recursive definition.

• To assist in deleting later, define a method called get_successor(self, curr_node). This method should return the value contained in the smallest value contained in the tree rooted at curr_node. This is the node that is the farthest "left" in this tree.
• Your delete method needs two phases. Phase 1 is finding the node to remove. This should be very similar to search.

The second phase is deletion. You have 4 conditions: No children, only a left child, only a right child, and both children. In the no children case, your method should return none. In only left or only right, you return the defined child. Otherwise, you have you find the successor value of the current node, place that data in the current node. Then set the right child of the current node as the result of deleting the successor value from the right sub-tree.

### Challenge

As you might have noticed, our trees can get quite out of balance. Especially if they are given a list of sorted elements. If we have a list of sorted elements inserted into the tree, our tree is going to almost look like a linked list. There are two ways to handle this issue: balance the trees, or randomly choose which elements to insert.

For now, let's take the simplified approach. Write a new method insert_randomly(self, a_list), which takes a list of elements to insert into the tree. Instead of iteratively inserting all of the elements of the list directly into the tree, insert them into the tree in some random order.

This only helps if it actually reduces how deep the tree actually is. Write a method height(self), which returns how long the longest branch of the tree is. Try inserting lists of size 100 into the tree. What is the average depth of the tree, using this random insert mechanism?

#### Submission

When you have finished, create a tar file of your lab27 directory. To create a tar file, execute the following commands:

cd ~/cs170/labs
tar czvf lab27.tgz lab27/


To submit your activity, go to inquire.roanoke.edu. You should see an available assignment called Lab Assignment 27. Make sure you include a header listing the authors of the file.