< Back

Lecture 28 - Binary Trees Continued

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

$ mkdir ~/cs170/labs/lab28 
$ cd ~/cs170/labs/lab28

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. However, visualizing the tree is a little harder than a list. Today, we are going to look at multiple ways to perform a traversal of a tree.

Lab Activity 1
Depth-First Traversal

Just like with linked lists, we have a mechanism for building our tree. However, we don't have a good way of visualizing it. We need some method for printing out the structure to the terminal. That was easy to think of for a linked list. However, that's less obvious for a tree...how do we represent a tree in text as a string.

There are actually a couple of ways to print a tree out to the terminal: Depth-first or Breadth-first. Usually, we stick to Depth-first. In depth-first traversals, we traverse down an entire branch before we cover another branch. The nice thing about depth-first traversal are that they can be written recursively.

There are three versions of Depth-first traversals: pre-order, in-order, and post-order. We are going to focus on pre-order for today. I will show off the other two in class on Wednesday.

Details

In the binary_tree.py file, write a method called pre_order(self), which returns a string representation of the tree using pre-order traversal techniques. You want the entire string to be represented on one line: You should not insert any new lines in the string.

Pre-order traversals print the data at the root of the tree before they print the data from the children. Consider the following tree

Thanks Wikipedia!

Pre-order traversal would first output an 'F', since F is at the root. Then, It would perform the same operation on the left child. This would produce a 'B'. And again, the same process would execute on the left child of 'B', producing 'A'. 'A' Doesn't have any children, so we would backtrack to 'B', and run that process on the right child of 'B', producing 'D'. The full, pre-order traversal is: 

F B A D C E G I H

Create some additional test cases to the one that I provide you below. Does the pre-order method of printing make sense? Can you easily draw the tree that a pre-order output represents? For the following pre-order strings, draw the represented tree in comments at the bottom of the binary_tree file:

Example

>>> my_tree = binary_tree.BinaryTree()
>>> my_tree.insert(5)
>>> my_tree.insert(3)
>>> my_tree.insert(8)
>>> my_tree.insert(4)
>>> print(my_tree.pre_order())
5 3 4 8

Hint

Again, this function is much easier to write recursively than iteratively. Again, you will need to write a helper function pre_order_helper(self, node), which takes a node and returns the string representation of the pre-order traversal from that node.

 

Challenge

The strings produced by the above algorithm are unambiguous. However, they can still take some time to parse. This is because a 2-dimensional structure is being represented by a 1-dimensional string. Maybe we can make this 2-dimensional?

Write a new method pre_order_2D(self), which returns a new string representation. Each piece of data will appear on its own line in this output, so if there are n nodes in the tree, there will be n lines in the output. For each piece of data output, you should output some number of spaces before the data. 2 spaces per depth seems to work well. You will need to write a helper function to accomplish this, and it will need to take additional parameters.

Example

>>> print(my_tree.pre_order_2D())
5 
  3 
    4 
  8
Lab Activity 2
Searching

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 BinaryTree 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 = BinaryTree()
>>> 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.

 

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 lab28 directory. To create a tar file, execute the following commands: 

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

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

Class Notes