## Lecture 26 - Binary Search Trees

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

  $mkdir ~/cs170/labs/lab26$ cd ~/cs170/labs/lab26


### Test Overview

Mean
74.5
Median
77
Standard Deviation
19.85

### Emacs Commands!

5 more Emacs commands for your benefit. Don't forget, you will get 5 questions next week from ALL emacs commands taught. Don't forget the old ones! The easiest way to remember these commands is to use them!

C-/ or C-_
Undo
C-a
C-e
M-<
M->

### Trees

Lists and Linked Lists are linear data structures. Data is associated with each other via the continuous nature of the structure. To get from one element, you need to traverse through all of the previous elements. However, not all information is related in such a linear way. Some data is better represented in a hierarchical manner. Today, you will begin learning about Trees: a hierarchical data structure similar to linked lists.

Lab Activity 1
Building a Binary Search Tree

A Binary Search Tree is a simple heirarchical data structure. In a Binary Search Tree, all nodes have at most 2 children. These are commonly referred to as the left and right children of that node. Another aspect of Binary Trees are the ordering of data: All of the data in the left sub-tree is less than (or equal to) the data in the parent, while all of the data in the right sub-tree is greater than the data in the parent.

Given this restriction on the ordering of data, you need to make sure things get inserted into the tree in the correct order. Luckly, this process is going to sound fairly familiar.

#### Details

In the binary_tree.py file (linked below), create a method in the BinarySearchTree class called insert(self, data). This method will take some data, and insert it into the correct location in the tree. Remember that all data is to be inserted at a leaf: Once the internal nodes are set, they cannot be changed.

Note that there are a couple of ways to accomplish this, but the easiest solution might (surprisingly) be recursive! You might need to write a helper function to accomplish this, however.

#### Example

  >>> my_tree = binary_tree.BinarySearchTree()
>>> my_tree.insert(5)
>>> my_tree.insert(3)
>>> my_tree.insert(8)
>>> print(my_tree.root.data)
5
>>> print(my_tree.root.left.data)
3
>>> print(my_tree.root.right.data)
8
>>> my_tree.insert(4)
>>> print(my_tree.root.left.right.data)
4


#### Hint

• You will need a special case for inserting the first element into the tree: Just create a node to represent the root of the tree.

• You can only insert data at the leaves of a binary tree. This means you need to traverse down the tree until you locate a leaf that you can insert it. Given a node r, if data is less than or equal to r.data, and r.left is None, create a node at r.left for data. Otherwise, try the same process on r.left.

the process for r.right is very similar.

• I know it may seem counter-intuitive for most of you, but the recursive definition is so elegant that I even have trouble thinking of the iterative manner of insertion. It is possible, however.

### Challenge

Binary Search Trees are actually how binary search gets its name. For a properly formatted tree, you can perform binary search in a tree in the same amount of time that we could perform it on a list. However, this requires a properly formatted tree...which is not a given with the above structure.

Write a method insert_list(self, a_sorted_list), which takes an ordered list of elements, and inserts them in the correct order for the binary tree to resemble a binary search. Do you notice anything interesting about this code?

Lab Activity 2
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 is 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

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:

• 1 2 3 4 5
• 1 5 4 2 3

#### Example

  >>> my_tree = binary_tree.BinarySearchTree()
>>> 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

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.

For the pre-order traversal, you start by add the data of the current node to your returned string. Then, you get the strings for the left and right sub-trees by recursively calling the pre_order_helper method with the left and right children. You add the strings these two methods return into your returned string.

### 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


#### Submission

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

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


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